Quick Sort Algorithm

What is Quick Sort?

Quick Sort is a highly efficient divide-and-conquer sorting algorithm. It is widely used due to its excellent performance in practice and ability to sort in-place. Quick Sort divides the array into smaller parts by selecting a pivot element, then rearranges (or “partitions”) the elements so that:

• Elements less than the pivot come before it
• Elements greater than the pivot come after it

The process is repeated recursively for the left and right parts until the entire array is sorted.

How Quick Sort Works

1. Choose a Pivot: Any element (commonly the middle or first).
2. Partition the Array: Rearrange elements so that:
   • Elements smaller than the pivot go to the left
   • Elements greater go to the right
3. Recursively Apply Quick Sort to the left and right partitions.

Why Use Quick Sort?

• Extremely fast for large datasets
• Performs in-place sorting (no extra memory needed)
• Average case time complexity of O(n log n)
• More efficient than Merge Sort in many real-world cases

Time & Space Complexity

• Space Complexity: O(log n) (due to recursive stack)
• In-Place: ✅ Yes
• Stable: ❌ No (equal elements may be reordered)

When to Use Quick Sort

• When performance matters more than stability
• When you need an efficient in-place sorting algorithm
• For large arrays with unpredictable patterns

Quick Sort – C++ Code Example

#include <iostream>
using namespace std;

// Function to swap two elements
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Partition function
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choose last element as pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// Quick Sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Partition the array
        int pi = partition(arr, low, high);

        // Sort the sub-arrays
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Utility function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Main function
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array:\n";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array:\n";
    printArray(arr, n);

    return 0;
}

Output

Original array:
10 7 8 9 1 5 
Sorted array:
1 5 7 8 9 10 

Quick Sort – Visual Explanation (Step-by-Step)

Let’s sort:

[10, 7, 8, 9, 1, 5]

Step 1: Choose Pivot

• Choose last element → pivot = 5
• Rearrange:
  • 10 > 5 → no action
  • 7 > 5 → no action
  • 8 > 5 → no action
  • 9 > 5 → no action
  • 1 < 5 → move 1 before pivot

After partitioning:

[1, 5, 8, 9, 10, 7]
→ Pivot 5 is at its correct position

Step 2: Recursively Sort Left Subarray [1] → already sorted

Step 3: Recursively Sort Right Subarray [8, 9, 10, 7]

• Pivot = 7
• 8 > 7, 9 > 7, 10 > 7 → nothing moves
• Place 7 in correct position

Result:

[1, 5, 7, 9, 10, 8]

Step 4: Recursively Sort [9, 10, 8]

• Pivot = 8
• 9 > 8, 10 > 8 → place 8 before them
  → Final result: [1, 5, 7, 8, 9, 10]

Final Sorted Array

[1, 5, 7, 8, 9, 10]

Summary

• Quick Sort is a fast, in-place, recursive sorting algorithm.
• It is based on partitioning around a pivot.
• Has excellent average-case performance: O(n log n)
• Commonly used in competitive programming and real-world systems.