Quick Sort is one of the most efficient and widely used algorithms in Computer Science. Unlike Bubble Sort, which iterates and swaps, Quick Sort uses a Divide and Conquer strategy. It works by selecting a "pivot" element and partitioning the array around it, such that smaller elements move to the left and larger elements move to the right.

Imagine a librarian trying to organize a messy pile of books. Instead of comparing every book to every other book, the librarian picks one random book (the pivot)—say, "Harry Potter". She then quickly throws every book alphabetically before Harry Potter into a left pile, and every book after it into a right pile. Now, "Harry Potter" is in its exact final spot. She then repeats this process for the left pile and the right pile until every book is shelved.

The core mechanism of Quick Sort is Partitioning. This process dictates how the array is split before the recursive calls are made.

• Pick a Pivot: The algorithm selects an element to serve as the reference point (commonly the last element, first element, or median).
• Rearrange: It scans the array. Any element smaller than the pivot is moved to the left side; any element larger is moved to the right side.
• Place Pivot: The pivot is placed in the "middle" between the two sections.
• Recursion: The algorithm recursively applies the same logic to the left sub-array and the right sub-array.

Let's trace the partitioning logic using the last element as the pivot.

Below is the implementation of Quick Sort in multiple programming languages. The partition function is the heart of the algorithm, efficiently rearranging elements around the pivot.

#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);
    }
}
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, n - 1);
    
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Quick Sort is generally preferred over Bubble Sort because of its superior average-case performance.

Time Complexity

Space Complexity

Quick Sort is often the default sorting algorithm in many standard libraries (like C++ std::sort or Java's Arrays.sort for primitives) because of its speed and cache efficiency.