Quick Sort

Quick sort is an efficient sorting algorithm based on the divide-and-conquer strategy. Its core idea is to select a pivot element, partition the sequence into two sub-sequences (left and right), such that all elements in the left sub-sequence are less than or equal to the pivot, and all elements in the right sub-sequence are greater than or equal to the pivot. Then, recursively apply the same operation to these two sub-sequences until the entire sequence is sorted.

Detailed Step-by-Step Breakdown

1. Basic Idea and Pivot Selection

   • First, select an element from the array (or sub-array) to be sorted as the "pivot". There are various ways to choose the pivot, such as always selecting the first element, the last element, the middle element, or randomly selecting an element. For ease of explanation, we typically choose the first element as the pivot. Suppose we have an array arr with left and right boundary indices left and right respectively (initially left = 0, right = arr.length - 1). We select pivot = arr[left] as the pivot.

2. Partitioning Operation - The Core Step
   Partitioning is the core of the quicksort algorithm. The goal is to rearrange the array so that all elements less than or equal to the pivot are on its left, and all elements greater than the pivot are on its right. The pivot element itself is placed in its final correct position. The index of this final position is called the partition point. We use the two-pointer method (using the Hoare partition scheme as an example) to achieve this:

   • Step 2.1: Initialize pointers. Set two pointers i and j. i starts from the leftmost end (left) and scans rightwards, looking for an element greater than the pivot; j starts from the rightmost end (right) and scans leftwards, looking for an element less than or equal to the pivot.
   • Step 2.2: Scan and Swap.
     • First, move pointer j from right to left until it finds the first element less than or equal to the pivot value pivot.
     • Then, move pointer i from left to right until it finds the first element greater than the pivot value pivot.
     • If at this point i is still less than j (meaning the pointers have not yet met or crossed), swap the values of arr[i] and arr[j]. This step exchanges a large element (on the left) with a small element (on the right), moving them closer to their correct sides.
   • Step 2.3: Repeat Scans. Repeat Step 2.2 (move j, then move i, then check and swap) until pointers i and j meet or cross (i.e., i >= j). At this point, scanning stops.
   • Step 2.4: Place the Pivot. After i and j meet, we need to place the pivot element in its final correct position. Note that in the Hoare partition scheme, the meeting point (the position of pointer j) typically guarantees that elements to its left are all less than or equal to the pivot. Therefore, we swap the pivot element arr[left] with arr[j]. After the swap, the pivot element pivot is now at index j. At this moment, the array is divided into three parts:
     • arr[left...j-1]: All elements <= pivot
     • arr[j]: The pivot element, now in its sorted, final position.
     • arr[j+1...right]: All elements > pivot

3. Recursive Sorting

   • Now, the pivot element is in its final position. Next, we recursively apply the same algorithm to the two sub-arrays to the left and right of the pivot.
   • Recursively perform quick sort on the left sub-array arr[left...j-1].
   • Recursively perform quick sort on the right sub-array arr[j+1...right].
   • Recursion Termination Condition: When a sub-array has a length of 0 or 1 (i.e., left >= right), it is naturally sorted, and no further recursion is needed.

Complete Example

Sorting the array [5, 2, 9, 1, 5, 6] in ascending order.

• Initial state: [5, 2, 9, 1, 5, 6], left=0, right=5, pivot=5 (first element).
• First Partition Round:
  • j moves right to left to find a number <=5. 6(index 5) >5, continue. 5(index 4) <=5, j stops at 4.
  • i moves left to right to find a number >5. 2(index 1) not >5, continue. 9(index 2) >5, i stops at 2.
  • i(2) < j(4), swap 9 and 5: array becomes [5, 2, 5, 1, 9, 6].
  • Continue. j moves from 4 leftwards. 9>5, continue. 1(index 3)<=5, j stops at 3.
  • i moves from 2 rightwards. 5 not >5, continue. i moves to 3.
  • Now i(3) >= j(3), scanning stops.
  • Swap the pivot arr[0](5) with the element 1 at arr[j](3): array becomes [1, 2, 5, 5, 9, 6]. Now the pivot 5 is at index 3.
  • Partition result: Left sub-array [1, 2] (indices 0-2), pivot 5 (index 3), right sub-array [9, 6] (indices 4-5).
• Recursively sort left sub-array [1, 2]:
  • pivot=1.
  • After partitioning, [1, 2]. 1 is already in its correct position. Left sub-array is empty, right sub-array is [2].
  • Recursively sort [2], a single element, returns directly. Left part done.
• Recursively sort right sub-array [9, 6]:
  • pivot=9.
  • After partitioning, swap 9 and 6, get [6, 9]. 9 is in correct position.
  • Left sub-array [6] is sorted. Right part done.
• Final sorted array: Combine all parts to get [1, 2, 5, 5, 6, 9].

Key Points Summary

• Time Complexity: Average and best case: O(n log n). Worst case (when the array is already sorted or reverse sorted, and the pivot is chosen poorly) degrades to O(n²). Random pivot selection can largely avoid the worst case.
• Space Complexity: Mainly the depth of the recursion call stack, average O(log n), worst case O(n).
• Stability: Quick sort is not a stable sorting algorithm because during the partitioning process, the relative order of equal elements might change (e.g., the relative order of the two 5s in the example above might change).