C++ Program For Quick Sort With Time Complexity

Sorting data is a fundamental operation in computer science, crucial for optimizing search operations, merging data, and presenting information in an organized manner. Among the various sorting algorithms, Quick Sort stands out for its efficiency in practice. In this article, you will learn how the Quick Sort algorithm works, implement it in C++, and understand its time complexity.

Problem Statement

The core problem is to efficiently arrange a list of n elements (numbers, strings, objects) in a specific order, typically ascending or descending. While simpler algorithms like Bubble Sort exist, they become prohibitively slow for large datasets. An efficient sorting algorithm is required to handle data volumes common in modern applications, minimizing processing time and resource usage.

Example

Consider an unsorted array of integers: [10, 7, 8, 9, 1, 5]. After applying a sorting algorithm like Quick Sort, the array should be ordered: [1, 5, 7, 8, 9, 10].

Background & Knowledge Prerequisites

To understand Quick Sort and its C++ implementation, familiarity with the following concepts is essential:

• C++ Basics: Variables, data types, functions, arrays.
• Recursion: Understanding how functions call themselves and the concept of a base case.
• Pointers/References: How to pass array segments to functions efficiently.
• Divide and Conquer Strategy: The general algorithmic paradigm Quick Sort employs.

Use Cases or Case Studies

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

• Database Systems: Used for sorting records based on specific keys, for example, ordering search results by date or relevance.
• File Systems: Employed to sort files and directories by name, size, or modification date.
• Numerical Computing: Often chosen for sorting large datasets in scientific simulations or data analysis tools.
• Compiler Optimization: Used in certain phases of compiler design where symbol tables or intermediate code need sorting.
• Graphics and Image Processing: For operations like z-buffering or sorting polygons by depth, although often specialized sorting networks or bucket sorts might also be used depending on context.

Solution Approaches

Quick Sort is a highly efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy. It picks an element as a pivot and partitions the given array around the picked pivot.

Quick Sort Algorithm

Quick Sort works by recursively dividing an array into two sub-arrays around a pivot element. All elements smaller than the pivot go to the left sub-array, and all elements larger go to the right.

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

// 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) {
    int pivot = arr[high]; // Choosing the last element as pivot
    int i = (low - 1);     // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than or equal to 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);
}

// 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) {
    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);
    }
}

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

int main() {
    // Step 1: Initialize 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: Apply Quick Sort
    quickSort(arr, 0, n - 1);

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

    // Another example
    std::vector<int> arr2 = {2, 8, 7, 1, 3, 5, 6, 4};
    n = arr2.size();

    std::cout << "\\nOriginal array 2: ";
    printArray(arr2);

    quickSort(arr2, 0, n - 1);

    std::cout << "Sorted array 2: ";
    printArray(arr2);

    return 0;
}

Run

Sample Output

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

Original array 2: 2 8 7 1 3 5 6 4 
Sorted array 2: 1 2 3 4 5 6 7 8

Stepwise Explanation

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

• This is the main recursive function.
• Base Case: If low is greater than or equal to high, the sub-array has one or zero elements and is already sorted, so the recursion stops.
• Partitioning: Calls the partition function, which selects a pivot, reorders the sub-array so that all elements smaller than the pivot come before it and all elements greater come after it. It returns the index of the pivot element (pi).
• Recursive Calls: Recursively calls quickSort for the sub-array to the left of the pivot (low to pi - 1) and the sub-array to the right of the pivot (pi + 1 to high).

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

• Pivot Selection: The last element of the current sub-array (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 track the position for elements smaller than the pivot.
• Iteration: It 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 less than or equal to the pivot, i is incremented, and arr[i] is swapped with arr[j]. This moves smaller elements to the left side.
• Pivot Placement: After the loop, arr[i + 1] (the first element greater than the pivot or the first empty slot if all elements are smaller) is swapped with the pivot (arr[high]). This places the pivot in its correct sorted position.
• Return: The function returns i + 1, which is the final index of the pivot.

Time Complexity Analysis

The efficiency of Quick Sort heavily depends on the choice of the pivot element.

• Best Case: O(n log n)
• This occurs when the partition process always picks the middle element or an element close to the middle as the pivot.
• In this scenario, the array is divided into two almost equal halves at each step.
• Each partition step takes O(n) time, and there are log n such divisions (levels of recursion).

• Average Case: O(n log n)
• On average, Quick Sort performs very well. Even with suboptimal pivot choices, as long as the splits are not consistently extremely unbalanced, the overall performance remains O(n log n).
• The constant factors involved are typically small, making it faster than other O(n log n) algorithms like Merge Sort in many practical scenarios.

• Worst Case: O(n^2)
• This occurs when the pivot selection consistently results in highly unbalanced partitions. For example, if the smallest or largest element is always chosen as the pivot.
• In this situation, one sub-array will always be empty (or have one element), and the other will contain n-1 elements.
• This leads to n levels of recursion, with each partition step still taking O(n) time, resulting in O(n * n) = O(n^2).
• This worst-case scenario can happen if the array is already sorted or reverse-sorted and the pivot is always chosen as the first or last element. Techniques like choosing a random pivot or the median-of-three can help mitigate this.

• Space Complexity: O(log n) (Average) / O(n) (Worst Case)
• Quick Sort is an in-place sorting algorithm, meaning it requires minimal additional memory.
• The space complexity is primarily due to the recursion stack.
• Average Case: O(log n) for the recursion stack depth.
• Worst Case: O(n) if the partitions are highly unbalanced, leading to a deep recursion stack.

Conclusion

Quick Sort is a powerful and widely used sorting algorithm known for its efficiency in practical applications. Its divide-and-conquer strategy, combined with an in-place partitioning approach, makes it a strong choice for many sorting tasks. While its worst-case time complexity is O(n^2), effective pivot selection strategies can almost always ensure an average-case O(n log n) performance, making it one of the fastest general-purpose sorting algorithms available.

Summary

• Quick Sort is a divide-and-conquer sorting algorithm.
• It partitions an array around a pivot element, placing smaller elements to its left and larger elements to its right.
• The partition function is key, responsible for pivot placement and rearrangement.
• It is a recursive algorithm, calling itself on the sub-arrays.
• Time Complexity:
• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n^2) (can be mitigated with good pivot selection)
• Space Complexity: O(log n) on average due to recursion stack.