Quick Sort

Quick sort is a highly efficient, comparison-based sorting algorithm that follows a divide-and-conquer approach. It is known for its average-case time complexity of O(n log n) and is widely used in practice for sorting large datasets.

Working

1. Choose a Pivot: Select an element from the array to serve as the pivot. The choice of the pivot can significantly affect the efficiency of the algorithm. Common pivot selection strategies include choosing the first element, the last element, the middle element, or a randomly selected element.
2. Partition the Array: Rearrange the elements in the array such that all elements less than the pivot are on the left side, and all elements greater than the pivot are on the right side. The pivot is now in its final sorted position. This process is called partitioning.
3. Recursively Sort Subarrays: Recursively apply the Quick Sort algorithm to the subarrays on the left and right sides of the pivot. These subarrays contain elements that are less than and greater than the pivot, respectively.
4. Combine Sorted Subarrays: As the subarrays are sorted recursively, they are combined to produce the final sorted array.

Coding:

#include <iostream>
#include <vector>
// Function to partition the array and return the index of the pivot element
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // Choose the last element as the pivot
    int i = low - 1; // Index of the smaller element
    for (int j = low; j < high; j++) {
        // If the current element is less than or equal to the pivot
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    // Swap the pivot element with the element at (i + 1), placing the pivot in its correct position
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}
// Function to perform Quick Sort
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // Partition the array and get the pivot index
        int pivotIndex = partition(arr, low, high);
        // Recursively sort the elements before and after the pivot
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}
int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    int n = arr.size();
    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    quickSort(arr, 0, n - 1);
    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Complexity

The Quick Sort algorithm has an average-case time complexity of O(n log n), which makes it highly efficient for sorting large datasets. However, it's important to note that the worst-case time complexity can be O(n^2) under certain conditions.

Let's break down the time complexity of Quick Sort in different scenarios:

Average-case time complexity (O(n log n))

On average, Quick Sort divides the array into roughly equal-sized partitions and sorts them. The average time complexity is O(n log n) because the algorithm makes log₂(n) recursive calls (where "n" is the number of elements in the array), and in each call, it performs a linear-time partitioning operation. This results in a balanced partitioning of the data and leads to efficient sorting.

Best-case time complexity (O(n log n))

The best-case scenario occurs when the pivot element chosen in each step splits the array into two roughly equal-sized subarrays. In this case, Quick Sort exhibits its optimal behavior with a time complexity of O(n log n).

Worst-case time complexity (O(n^2))

The worst-case scenario happens when the pivot element is always chosen as the smallest or largest element in the array. This leads to unbalanced partitioning, and in extreme cases, Quick Sort may make n recursive calls, each processing only one element. This results in a quadratic time complexity of O(n^2). However, this worst-case scenario is relatively rare in practice, especially if pivot selection strategies like randomization or median-of-three are used.

Space complexity (O(log n))

Quick Sort is generally an in-place sorting algorithm, which means it doesn't require additional memory proportional to the size of the input array. The space complexity is O(log n) because of the recursion stack, which can grow to a depth of log₂(n) due to the recursive nature of the algorithm. This space usage is relatively small and constant for large datasets.