Quick Sort

Concept

Quick Sort is an efficient, comparison-based sorting algorithm that uses a divide-and-conquer approach. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Characteristics

• Time Complexity:
  • Worst-case: O(n²)
  • Average-case: O(n log n)
  • Best-case: O(n log n)
• Space Complexity: O(log n) (due to the call stack)
• Stability: Not stable (can be implemented as stable with extra space)
• In-place sorting algorithm (minimal extra memory required).

Code Example (C++)

#include <iostream>
#include <vector>
#include <algorithm>

// Function to partition the array
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // Choose the rightmost element as the pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // If the current element is smaller than or equal to the pivot
        if (arr[j] <= pivot) {
            i++; // Increment index of smaller element
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// Quick Sort function
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);

        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Helper function to print the vector
void printVector(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> data = {10, 7, 8, 9, 1, 5};
    std::cout << "Unsorted array: ";
    printVector(data);

    quickSort(data, 0, data.size() - 1);

    std::cout << "Sorted array: ";
    printVector(data);

    return 0;
}
// To compile and run (e.g., with g++):
// g++ your_file_name.cpp -o quick_sort_cpp
// ./quick_sort_cpp

Code Example (Python)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)

        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

# Example usage:
if __name__ == "__main__":
    data = [10, 7, 8, 9, 1, 5]
    print("Unsorted array:", data)

    quickSort(data, 0, len(data) - 1)

    print("Sorted array:", data)

# To run:
# python your_file_name.py