Learn Quick Sort in 13 minutes ⚡

Key Concepts QuickSort, Pivot, Partitioning, In-place sorting, Recursion, Divide and Conquer, Indices (i, j), Temporary variable, Swap, Base case, Call stack, Runtime Complexity (Big O notation), Space Complexity (Big O notation).

Understanding the QuickSort Algorithm

The QuickSort algorithm is a recursive, divide-and-conquer sorting method applied to an array or collection. The process begins by passing an unordered array into a QuickSort function.

1. Pivot Selection: A crucial step is selecting a "pivot" element. While variations allow picking the pivot from the beginning, middle, or end, most standard QuickSort algorithms set the pivot to be the last element of the current array segment (or partition).

2. Finding the Pivot's Final Resting Place: The primary goal is to determine the pivot's correct sorted position within the array. This involves:

• Declaring two indices: j starts at the beginning of the array, and i starts one position before the beginning (start - 1).
• Utilizing a temporary variable (temp) for swapping values.
• Iteration Process:
  1. Index j iterates from the start of the array up to (but not including) the pivot's initial position (end - 1).
  2. For each element array[j]:
     • If array[j] is less than the pivot, i is incremented, and array[i] is swapped with array[j]. This ensures smaller elements move to the left side.
     • If array[j] is greater than or equal to the pivot, array[j] is ignored, and j simply increments.
• Final Placement: After j has iterated through the relevant segment, i is incremented one last time. The element at array[i] is then swapped with the original pivot (which was at array[end]).
• Verification: Once the pivot is in place, all elements to its left should be less than the pivot, and all elements to its right should be greater than or equal to the pivot. These sub-segments are not necessarily sorted internally yet.

3. Partitioning and Recursion: After the pivot is correctly positioned, the array is divided into two "partitions":

• Left Partition: Contains all elements from the beginning of the array up to pivotIndex - 1.
• Right Partition: Contains all elements from pivotIndex + 1 to the end of the array. QuickSort is a recursive divide and conquer algorithm. Unlike Merge Sort, which creates new subarrays, QuickSort sorts these partitions in place. The QuickSort function is then recursively called for each of these new partitions, using their respective beginning and ending indices as arguments. This process repeats until partitions are small enough (base case).

Coding the QuickSort Algorithm

To implement QuickSort, two main functions are typically used: a primary QuickSort function and a helper partition function.

1. QuickSort Function (private static void QuickSort(int[] array, int start, int end)):

• Parameters: Takes the array, a starting index, and an ending index for the current segment.
• Base Case: The recursion stops if end <= start. This means the segment has one or zero elements and is inherently sorted, so the function returns.
• Core Logic:
  1. Calls the partition helper function: int pivotIndex = partition(array, start, end);. This call sorts the current segment in place and returns the final index of the pivot.
  2. Recursively calls QuickSort for the left partition: QuickSort(array, start, pivotIndex - 1);. The pivot itself is excluded as it's already in its final position.
  3. Recursively calls QuickSort for the right partition: QuickSort(array, pivotIndex + 1, end);. Again, the pivot is excluded.

2. partition Helper Function (private static int partition(int[] array, int start, int end)):

• Purpose: This function is responsible for selecting a pivot, rearranging elements around it, and placing the pivot in its final sorted position. It returns the pivot's final index.
• Implementation Details:
  1. int pivot = array[end]; (The pivot is chosen as the last element of the current segment).
  2. int i = start - 1; (Index i tracks the boundary for elements smaller than the pivot).
  3. A for loop iterates j from start to end - 1:
     • if (array[j] < pivot):
       • i++;
       • Perform a swap between array[i] and array[j] using a temp variable: int temp = array[i]; array[i] = array[j]; array[j] = temp;
  4. After the loop, i++;
  5. Perform a final swap to place the pivot in its correct position: int temp = array[i]; array[i] = array[end]; (Moves the original pivot to array[i]) array[end] = temp; (Moves the element that was at array[i] to the original pivot's position)
  6. return i; (Returns the final index of the pivot).

Conclusion and Complexity Analysis

The QuickSort algorithm efficiently sorts an array by repeatedly partitioning it around a pivot element, ensuring smaller elements are to the left and larger elements to the right. This process is applied recursively to the resulting sub-partitions.

Runtime Complexity:

• Best and Average Case: O(N log N). This is the typical performance.
• Worst Case: O(N^2). This occurs rarely, primarily when the input array is already sorted or nearly sorted, leading to unbalanced partitions.

Space Complexity:

• O(log N). Although QuickSort sorts "in place" (meaning it doesn't create new arrays like Merge Sort), its recursive nature utilizes the call stack to store function frames. The depth of this recursion, and thus the memory usage, is proportional to the logarithm of the number of elements (N) in the average case. This makes its space complexity higher than simpler in-place sorts like Bubble Sort, Selection Sort, or Insertion Sort.