Lab assignment, Java, Activity selection, Quick sort, Simulation, Algorithm, Data structure, Programming, Computer science, Sorting algorithm, Greedy algorithm, Java lab report

QuickSort Simulation – Descending Order
Input Array: [45, -1, 45, 3, 31, -13, -134, 5]



Rules (Descending):
① i → moves RIGHT while arr[i] > pivot (stop when arr[i] ≤ pivot)
② j ← moves LEFT while arr[j] < pivot (stop when arr[j] ≥ pivot)
③ if i < j : swap arr[i] and arr[j], then continue
④ if j < i (j crosses i) : STOP – swap pivot with arr[j] (pivot is placed ✓)

Pass
Initial: 1 : Partitioning full array (pivot = 45)

45 -1 45 3 31 -13 -134 5
P i j
Pivot = 45 (index 0) | i starts at 1, j starts at 7

i: arr[1]=-1 ≤ 45 → i STOPS at 1 (found element ≤ pivot)
j: arr[7]=5, arr[6]=-134, arr[5]=-13, arr[4]=31, arr[3]=3 all < 45 → keep moving
arr[2]=45 is NOT < 45 → j STOPS at 2
i & j stopped:

45 -1 45 3 31 -13 -134 5
P i j


i(1) < j(2) → Swap arr[1]=-1 ↔ arr[2]=45
After swap:

45 45 -1 3 31 -13 -134 5
P j i
Now i=2, j=1 → j < i : CROSSED → swap pivot with arr[j=1]
Pivot placed:

45 45 -1 3 31 -13 -134 5
P
■ Pivot 45 is now at index 1 ✓
Left sub-array : [45] (index 0) ← already sorted (single element)
Right sub-array : [-1, 3, 31, -13, -134, 5] (indices 2–7) → recurse