C++ Program For Quick Sort Using Recursion

Quick Sort is an efficient, comparison-based sorting algorithm that employs a divide-and-conquer strategy. It is known for its average-case time complexity of O(n log n). In this article, you will learn how to implement Quick Sort in C++ using recursion, understand its underlying principles, and see a practical example.

Problem Statement

The fundamental problem addressed by sorting algorithms like Quick Sort is to arrange elements of a list or array in a specific order (e.g., ascending or descending). Efficiently sorting large datasets is crucial in many computing applications, from database indexing to search algorithms, where poorly sorted data can lead to significant performance bottlenecks.

Example

Consider an unsorted array: [10, 7, 8, 9, 1, 5]. After applying Quick Sort, the array will be sorted in ascending order: [1, 5, 7, 8, 9, 10].

Background & Knowledge Prerequisites

To understand Quick Sort using recursion, it's beneficial to have a grasp of:

• C++ Basics: Variables, arrays, loops, and functions.
• Recursion: The concept of a function calling itself to solve smaller subproblems.
• Pointers or References: For manipulating array elements efficiently.
• Divide and Conquer: A general problem-solving paradigm where a problem is broken into smaller subproblems until they become simple enough to solve directly.

Use Cases or Case Studies

Quick Sort is widely used in various applications due to its efficiency:

• Standard Library Sorts: Many programming language standard libraries (e.g., C++ std::sort often use Introsort, which is a hybrid algorithm leveraging Quick Sort for its average-case performance).
• Database Systems: For sorting records based on specific keys, which is vital for indexing and query optimization.
• Search Algorithms: Pre-sorting data significantly speeds up search operations (e.g., binary search).
• Numerical Computations: Used in algorithms that require data to be ordered, such as median finding or percentile calculations.
• Graphics and Image Processing: For sorting pixels based on intensity or color values for certain effects or analyses.

Solution Approaches

We will focus on the classic recursive Quick Sort algorithm, which partitions an array around a 'pivot' element and then recursively sorts the sub-arrays.

Recursive Quick Sort Implementation

This approach utilizes a pivot element to divide the array into two sub-arrays: elements smaller than the pivot and elements greater than the pivot. It then recursively sorts these sub-arrays.

// Quick Sort using Recursion
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

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

// Function to partition the array
// It takes the last element as pivot, places the pivot element at its correct
// position in sorted array, and places all smaller (than pivot) to left of
// pivot and all greater elements to right of pivot
int partition(std::vector<int>& arr, int low, int high) {
    // Step 1: Choose the pivot (last element in this case)
    int pivot = arr[high];
    // Index of smaller element and indicates the right position of the pivot found so far
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        // Step 2: If current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++; // Increment index of smaller element
            std::swap(arr[i], arr[j]);
        }
    }
    // Step 3: Place the pivot at its correct position
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// The main function that implements QuickSort
// arr[] --> Array to be sorted, low --> Starting index, high --> Ending index
void quickSort(std::vector<int>& arr, int low, int high) {
    // Step 1: Base case for recursion: if low >= high, the sub-array has 0 or 1 elements, so it's already sorted.
    if (low < high) {
        // Step 2: Partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);

        // Step 3: Recursively sort elements before partition and after partition
        quickSort(arr, low, pi - 1);  // Sort the left sub-array
        quickSort(arr, pi + 1, high); // Sort the right sub-array
    }
}

int main() {
    // Step 1: Define an unsorted array
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    std::cout << "Original array: ";
    printArray(arr);

    // Step 2: Call quickSort function to sort the array
    quickSort(arr, 0, n - 1);

    std::cout << "Sorted array: ";
    printArray(arr);

    return 0;
}

Run

Sample Output:

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

Stepwise Explanation:

1. quickSort(arr, low, high) Function:

• This is the main recursive function. It takes the array, a low index (start of the sub-array), and a high index (end of the sub-array).
• Base Case: If low is greater than or equal to high, it means the sub-array has 0 or 1 elements, which is already sorted. The recursion stops here.
• Partition: It calls the partition function, which rearranges elements such that the pivot element is in its correct sorted position. The partition function returns the index of this pivot.
• Recursive Calls: It then recursively calls quickSort for the sub-array to the left of the pivot (low to pi - 1) and for the sub-array to the right of the pivot (pi + 1 to high).

1. partition(arr, low, high) Function:

• Pivot Selection: In this implementation, the last element (arr[high]) is chosen as the pivot. Other strategies include choosing the first element, a random element, or the median-of-three.
• Initialization: An index i is initialized to low - 1. This i will keep track of the boundary between elements smaller than the pivot and elements greater than the pivot.
• Iteration: The function iterates through the sub-array from low to high - 1 (excluding the pivot).
• Comparison and Swap: If an element arr[j] is found to be smaller than the pivot, i is incremented, and arr[i] is swapped with arr[j]. This effectively moves smaller elements to the left side of i.
• Pivot Placement: After the loop, all elements smaller than the pivot are to the left of i, and all elements greater are to the right. The pivot (arr[high]) is then swapped with arr[i + 1], placing the pivot in its final sorted position.
• Return: The function returns i + 1, which is the final index of the pivot.

1. main() Function:

• An example std::vector is initialized.
• The quickSort function is called with the array, the starting index 0, and the ending index n - 1.
• The sorted array is then printed.

Conclusion

Quick Sort is a powerful and widely used sorting algorithm, particularly effective for large datasets due to its average-case O(n log n) time complexity. Its recursive nature, combined with the efficient partition operation, allows it to divide and conquer the sorting problem effectively. While its worst-case performance is O(n^2), proper pivot selection strategies can usually mitigate this risk, making it a highly practical choice for many applications.

Summary

• Quick Sort is a divide-and-conquer sorting algorithm with an average time complexity of O(n log n).
• It works by partitioning an array around a pivot element and recursively sorting the resulting sub-arrays.
• The partition function is key; it places the pivot in its correct sorted position and arranges elements smaller than the pivot to its left and larger elements to its right.
• Recursion is used to sort the sub-arrays until the base case (sub-array of 0 or 1 element) is reached.
• Despite a worst-case O(n^2) complexity, Quick Sort is often preferred for its in-place sorting and good average performance.