Introduction

Quick Sort is a highly efficient sorting algorithm that follows the divide-and-conquer approach to organize data. It works by selecting a pivot element and partitioning the array such that elements smaller than the pivot are placed on its left, and those greater are on its right. This process is recursively applied to the sub-arrays formed by the partition. Quick Sort is known for its excellent average-case performance and is widely used for sorting large datasets due to its in-place sorting capability and relatively low memory usage.

Complexity

• Best Case: O(n log n) [Occurs when the pivot divides the array into two nearly equal halves every time.]
• Average Case: O(n log n) [This is the most common scenario when pivots are chosen randomly or using median-of-three.]
• Worst Case: O(n²) [Happens when the pivot is always the smallest or largest element, such as when the array is already sorted.]
• Space Complexity: O(log n) [Due to recursive function calls on the call stack. In the worst case, it can go up to O(n) if recursion is unbalanced.]

Algorithm Steps

• Choose a pivot element: Select a pivot from the array (e.g., first, last, or random element).

• Partition the array: Rearrange elements so that smaller ones are on the left of the pivot and larger ones on the right.

• Place the pivot correctly: Position the pivot in its sorted place within the array.

• Recursively sort left sub-array: Apply Quick Sort to the sub-array of elements less than the pivot.

• Recursively sort right sub-array: Apply Quick Sort to the sub-array of elements greater than the pivot.

• Repeat until base case: Stop recursion when sub-arrays have zero or one element.

Example Array

[7, 2, 1, 6, 8, 5, 3, 4]

Let’s apply Quick Sort step-by-step (dry run) using the last element as the pivot.

Initial Call:

quickSort(arr, 0, 7)

Pivot = 4

Partitioning:

• Compare and swap elements so that values < 4 go to the left.
• After partition: [2, 1, 3] [4] [7, 6, 8, 5]

Now pivot 4 is at its correct position (index 3).

Left Sub-array:

quickSort(arr, 0, 2)

Sub-array = [2, 1, 3], Pivot = 3

Partitioning:

• Rearranged: [2, 1] [3]
• Pivot 3 placed at index 2

Left of 3:

quickSort(arr, 0, 1)

• Sub-array = [2, 1], Pivot = 1
• Swap to get [1, 2]

Pivot 1 placed at index 0

Left and right sub-arrays of 1 are size 0 — no further action.

Right Sub-array of 4:

quickSort(arr, 4, 7)

• Sub-array = [7, 6, 8, 5], Pivot = 5

Partitioning:

• Rearranged: [5] at correct position (index 4)
• Left: [], Right: [7, 6, 8]

Right of 5:

quickSort(arr, 5, 7)

• Sub-array = [7, 6, 8], Pivot = 8
• After partition: [7, 6] [8]
• Pivot 8 placed at index 7

Left of 8:

quickSort(arr, 5, 6)

• Sub-array = [7, 6], Pivot = 6
• Swap to get [6, 7]
• Pivot 6 placed at index 5

Final Sorted Array:

[1, 2, 3, 4, 5, 6, 7, 8]

✅ Advantages of Quick Sort:

• Fast in Practice: Quick Sort is generally faster than other sorting algorithms like Merge Sort and Bubble Sort for large datasets.
• In-Place Sorting: It doesn't require extra space like Merge Sort; sorting is done within the original array (space complexity: O(log n)).
• Efficient for Large Data: Performs well with large lists due to its average-case time complexity of O(n log n).
• Tail Recursion Optimization: Many implementations can be optimized to use less stack space through tail recursion.
• Cache-Friendly: Works well with modern memory hierarchies due to sequential access patterns.

❌ Disadvantages of Quick Sort:

• Worst-Case Time Complexity is O(n²): If the pivot is poorly chosen (e.g., smallest/largest element repeatedly), performance degrades significantly.
• Not Stable: It doesn’t preserve the relative order of equal elements (unlike Merge Sort or Insertion Sort).
• Recursive: Deep recursion may lead to stack overflow on very large inputs without optimization.
• Random Pivot Needed for Safety: To avoid worst-case scenarios, a randomized pivot selection is often required, which adds a bit of complexity.

Code in C :

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {7, 2, 1, 6, 8, 5, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, n - 1);
    printArray(arr, n);
    
    return 0;
}

Code in JAVA :

public class QuickSort {
    
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

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

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    static void printArray(int[] arr) {
        for (int value : arr)
            System.out.print(value + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {7, 2, 1, 6, 8, 5, 3, 4};
        quickSort(arr, 0, arr.length - 1);
        printArray(arr);
    }
}

Code in C++ :

#include <iostream>
using namespace std;

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

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

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {7, 2, 1, 6, 8, 5, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, n - 1);
    printArray(arr, n);
    
    return 0;
}

• for more topics Click Here.

Happy Coding!!