C++ Program For Quick Sort Algorithm In Data Structure

Quick Sort is a highly efficient, comparison-based sorting algorithm crucial for organizing data effectively. It employs a divide-and-conquer strategy, making it a popular choice for various applications due to its speed in average cases. In this article, you will learn how Quick Sort works and how to implement it in C++.

Problem Statement

Efficiently sorting a collection of elements is a fundamental problem in computer science. Unsorted data can significantly hinder performance in tasks such as searching, merging, and data retrieval. The challenge lies in developing an algorithm that can sort elements in an array or list in ascending or descending order with optimal time and space complexity.

Example

Consider an unsorted array of integers: [10, 7, 8, 9, 1, 5]. After applying the Quick Sort algorithm, the array will be sorted as: [1, 5, 7, 8, 9, 10].

Background & Knowledge Prerequisites

To understand Quick Sort, readers should have a basic grasp of:

• C++ Fundamentals: Variables, data types, arrays, loops, and functions.
• Recursion: Understanding how functions call themselves and the concept of base cases.
• Pointers and Array Indexing: How to access and manipulate elements within an array.
• Algorithms Basics: Familiarity with the concept of algorithms and their analysis (e.g., time complexity).

Use Cases or Case Studies

Quick Sort is widely used across various domains due to its efficiency:

• Database Management Systems: Used for sorting records based on specific keys, which is vital for indexing and optimizing query performance.
• Searching Algorithms: Many efficient searching algorithms, like binary search, require sorted data as a prerequisite. Quick Sort prepares data for such searches.
• Computational Geometry: In algorithms dealing with geometric data, sorting points or vectors is often a preliminary step.
• Data Analysis and Statistics: Sorting datasets is essential for calculating medians, percentiles, or for preparing data for further statistical analysis.
• Operating Systems: Used in various internal operations, such as process scheduling or memory management, where elements need to be ordered.

Solution Approaches

Quick Sort Algorithm Implementation

Quick Sort is a divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around it, recursively sorting the sub-arrays.

// Quick Sort Algorithm
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::swap

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

// Function to partition the array on the basis of a 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);
    }
}

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

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

    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. Choose a Pivot: The algorithm first selects an element from the array to be the 'pivot'. In this implementation, the last element of the sub-array is chosen as the pivot.
2. Partitioning: The goal of partitioning is to rearrange the elements in the array such that all elements smaller than the pivot come before it, and all elements greater than the pivot come after it. The pivot ends up in its final sorted position.

• An index i is maintained, initialized to low - 1. This i tracks the rightmost element that is smaller than or equal to the pivot.
• The loop iterates from low to high - 1. If an element arr[j] is found to be less than or equal to the pivot, i is incremented, and arr[j] is swapped with arr[i]. This ensures that arr[i] (and all elements to its left) are less than or equal to the pivot.
• Finally, the pivot (arr[high]) is swapped with arr[i+1], placing the pivot in its correct sorted position. The index i+1 is returned as the partitioning index.

1. Recursive Sorting: After partitioning, the array is divided into two sub-arrays: one containing elements smaller than the pivot and one containing elements larger than the pivot. Quick Sort is then recursively called on these two sub-arrays.
2. Base Case: The recursion stops when a sub-array has zero or one element, as such an array is already considered sorted.

Conclusion

Quick Sort is an efficient and widely-used sorting algorithm based on the divide-and-conquer paradigm. Its average-case time complexity of O(n log n) makes it very suitable for large datasets, though its worst-case scenario can degrade to O(n^2). The choice of pivot heavily influences performance, and various strategies exist to mitigate worst-case scenarios.

Summary

• Divide and Conquer: Quick Sort employs a recursive strategy to break down the problem into smaller, manageable sub-problems.
• Pivot Selection: A key element, the 'pivot,' is chosen to partition the array. Its position after partitioning is its final sorted position.
• Partitioning: Elements are rearranged such that all elements smaller than the pivot are on one side, and all greater elements are on the other.
• Time Complexity:
• Average Case: O(n log n), making it very fast for typical inputs.
• Worst Case: O(n^2), which occurs if the pivot selection consistently results in highly unbalanced partitions (e.g., already sorted array with last element as pivot).
• Space Complexity: O(log n) on average due to recursion stack, O(n) in the worst case.
• In-Place Sorting: It typically performs sorting by modifying the input array directly, requiring minimal additional memory.