Quick Sort

Time complexity: O(n log n)

Space complexity: O(log n)

Data type: Arrays

Visualization

Comparisons: 0

Reorders: 0

Delay: 1ms

Items: 50

Definition

Quick sort is a sorting algorithm that divides an array into smaller subarrays based on a pivot element. Quick sort selects a pivot, then partitions the array so that elements less than the pivot are on its left and elements greater than the pivot are on its right. The algorithm then recursively sorts the subarrays on either side of the pivot until the entire array is ordered. If a subarray has zero or one elements, it is already sorted and requires no further partitioning.

Constraints

  • Performance depends heavily on pivot selection, as a bad pivot can degrade efficiency
  • Not ideal for linked lists due to slow random access and poor cache performance during partitioning
  • Recursive implementation can lead to stack overflow for very large arrays due to deep recursion

Step-by-step explanation

Arguments:

  • Array to be sorted - array
  • Starting index - low
  • Ending index - high
  • Pivot element - pivot
  • Left partition (elements ≤ pivot) - left
  • Right partition (elements > pivot) - right

Explanation:

  • Select a pivot element from the array, typically array[high] or a random index
  • Partition the array into two subarrays around the pivot:
    • Elements less than the pivot go to the left of pivot
    • Elements greater than the pivot go to the right of pivot
  • Recursively apply QuickSort to the left subarray array[low..pivotIndex - 1]
  • Recursively apply QuickSort to the right subarray array[pivotIndex + 1..high]
  • Repeat until subarrays have 0 or 1 element (base case)

Returns:

Returns nothing (sorts array in-place)
Modifies the original array instead of returning a new one
No explicit return value (void function in most implementations)

Example

1
void quickSort(int arr[], int low, int high) {
2
    // Create a stack of pairs to store low and high indices
3
    std::stack<std::pair<int, int>> stack;
4
    
5
    // Push initial low and high to stack
6
    stack.push(std::make_pair(low, high));
7
    
8
    while (!stack.empty()) {
9
        // Pop low and high
10
        low = stack.top().first;
11
        high = stack.top().second;
12
        stack.pop();
13
        
14
        // Partition the array
15
        int pivot = arr[high]; // Choose last element as pivot
16
        int i = low - 1; // Index of smaller element
17
        
18
        for (int j = low; j <= high - 1; j++) {
19
            // If current element is smaller than or equal to pivot
20
            if (arr[j] <= pivot) {
21
                i++; // increment index of smaller element
22
                std::swap(arr[i], arr[j]);
23
            }
24
        }
25
        std::swap(arr[i + 1], arr[high]);
26
        int partitionIndex = i + 1;
27
        
28
        // Push subarrays to stack if they have more than one element
29
        if (partitionIndex - 1 > low) {
30
            stack.push(std::make_pair(low, partitionIndex - 1));
31
        }
32
        if (partitionIndex + 1 < high) {
33
            stack.push(std::make_pair(partitionIndex + 1, high));
34
        }
35
    }
36
}