Q14Data Structures

Quick Sort is a highly efficient, recursively driven divide-and-conquer algorithm. Its core mechanic revolves around selecting a "pivot" element from the array, and physically partitioning all other elements such that values smaller than the pivot reside to its left, and values larger reside to its right. This specific partitioning action guarantees that the chosen pivot is placed in its absolute, final, correct sorted location. The array provided is: [28, 5, 16, 36, 11, 19, 25].

Initial Partitioning (Pass 1)

We conventionally select the absolute first element as our primary pivot. Pivot: 28. We initialize two tracking pointers: left scanning forward from index 1, and right scanning backward from the final index.

The algorithmic goal is to locate an element > 28 from the left, and an element < 28 from the right, and violently swap them. left scans forward: 5, 16... halts at 36 (because 36 > 28). right scans backward: halts immediately at 25 (because 25 < 28). Swap Condition Met: We physically swap the values at the left and right pointers: 36 and 25.

Array becomes: [28 | 5, 16, 25, 11, 19, 36]. We resume scanning. left moves forward from 25: 11, 19, 36. Halts at 36. right moves backward from 36: 19. Halts at 19. At this exact juncture, the right pointer has structurally crossed over the left pointer (right < left). This physical crossing signifies the definitive end of the current partitioning phase. We conclude by swapping the original Pivot (28) with the element currently residing at the right pointer (19).

Array becomes: [19, 5, 16, 25, 11] | 28 | [36].

The pivot 28 is now permanently locked in its correct sorted position. We now recursively apply the exact same algorithm to the newly created left and right subarrays.

Recursive Sorting of Subarrays

Solving the Left Subarray: [19, 5, 16, 25, 11] New Pivot: 19. left halts at 25 (>19). right halts at 11 (<19). Swap them. Array: [19 | 5, 16, 11, 25]. left halts at 25. right halts at 11. Pointers mathematically cross. Swap Pivot 19 with right pointer 11. Result: [11, 5, 16] | 19 | [25]. 19 is locked.

Solving Sub-Subarray: [11, 5, 16] New Pivot: 11. left halts at 16 (>11). right halts at 5 (<11). Pointers immediately cross. Swap Pivot 11 with right pointer 5. Result: [5] | 11 | [16]. All elements single, thus sorted.

The overall recursively sorted array flawlessly merges back together, yielding the final ordered sequence: [5, 11, 16, 19, 25, 28, 36].