C++ Program For Quick Sort In Ascending Order

Quick Sort is a highly efficient, comparison-based sorting algorithm. Known for its average-case performance, it's a popular choice for arranging data.

In this article, you will learn how to implement Quick Sort in C++ to sort an array of integers in ascending order.

Problem Statement

Efficiently arranging a large collection of data, such as numbers in an array, is a fundamental problem in computer science. When dealing with unsorted data, operations like searching and finding minimum/maximum elements become significantly slower. The goal is to transform an unsorted array into a sorted one using a performant algorithm.

Example

Consider an unsorted array of integers: [10, 7, 8, 9, 1, 5]. After applying Quick Sort in ascending order, the array should become: [1, 5, 7, 8, 9, 10].

Background & Knowledge Prerequisites

To understand Quick Sort, readers should be familiar with:

• C++ Basics: Fundamental syntax, data types (especially arrays), and function definitions.
• Recursion: The concept of a function calling itself, including base cases and recursive steps.
• Pointers and References (Optional but helpful): For understanding how array elements are manipulated efficiently in memory.

Use Cases or Case Studies

Quick Sort is widely used in various applications due to its speed and efficiency.

• Database Management Systems: Used for sorting query results before presentation, especially when large datasets are involved.
• Data Analysis and Scientific Computing: Efficiently sorting datasets is crucial for statistical analysis, machine learning preprocessing, and numerical simulations.
• Operating Systems: Employed in tasks like scheduling processes by priority or sorting file lists by name or size.
• Competitive Programming: A go-to sorting algorithm due to its average-case time complexity, often implemented from scratch.
• Graphics and Image Processing: Used for sorting pixel data based on certain criteria, such as intensity or color components.

Solution Approaches

Quick Sort works on the principle of Divide and Conquer. It picks an element as a pivot and partitions the given array around the picked pivot. There are different ways to choose the pivot (e.g., first element, last element, middle element, random element) and different partitioning schemes (e.g., Lomuto partition scheme, Hoare partition scheme). We will use the Lomuto partition scheme with the last element as the pivot.

1. Standard Quick Sort Implementation

This approach involves two main functions: a partition function that rearranges elements around a pivot, and the main quickSort function that recursively calls itself on sub-arrays.

One-line Summary

The partition function places the pivot element at its correct sorted position and arranges all smaller elements to its left and all greater elements to its right; quickSort then recursively sorts these two partitions.

Code Example

// Quick Sort in C++
#include <iostream>
#include <vector> // Using std::vector for dynamic array
#include <algorithm> // For std::swap

// Function to swap two elements
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

/* This function takes 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]; // Pivot is the last element
    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
            swap(&arr[i], &arr[j]);
        }
    }
    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 i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    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();

    // Step 2: Print the original array
    std::cout << "Original array: ";
    printArray(arr);

    // Step 3: Apply Quick Sort
    quickSort(arr, 0, n - 1);

    // Step 4: Print the sorted array
    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. swap(int* a, int* b) function: A utility function to exchange the values of two integer pointers. This is used within the partition function.
2. partition(std::vector& arr, int low, int high) function:

• It selects the last element arr[high] as the pivot.
• It initializes i (index of smaller element) to low - 1.
• It iterates from j = low to high - 1. If arr[j] is less than or equal to the pivot, i is incremented, and arr[i] and arr[j] are swapped. This places elements smaller than or equal to the pivot on the left side of i.
• After the loop, the pivot element (arr[high]) is swapped with the element at arr[i + 1]. This places the pivot in its final sorted position.
• The function returns i + 1, which is the index of the pivot element.

1. quickSort(std::vector& arr, int low, int high) function:

• This is the recursive function. Its base case is if (low < high). If low is not less than high, it means there's 0 or 1 element, which is already sorted.
• It calls the partition function, which rearranges the sub-array arr[low...high] and returns the index pi of the pivot.
• It then recursively calls quickSort for the sub-array before the pivot (arr[low...pi-1]).
• Finally, it recursively calls quickSort for the sub-array after the pivot (arr[pi+1...high]).

1. main() function:

• Initializes a std::vector with unsorted integers.
• Prints the original array.
• Calls quickSort with the array, starting index (0), and ending index (n-1).
• Prints the sorted array.

Conclusion

Quick Sort stands as a powerful and efficient sorting algorithm, relying on the elegant divide-and-conquer strategy. By understanding its core components—pivot selection and partitioning—you can effectively sort data in ascending order in C++. Its average-case performance makes it a preferred choice for many real-world sorting requirements.

Summary

• Algorithm Type: Comparison-based, Divide and Conquer.
• Core Idea: Pick a pivot, partition the array around it, and recursively sort sub-arrays.
• Time Complexity (Average Case): O(N log N), making it very efficient for large datasets.
• Time Complexity (Worst Case): O(N^2), occurring when the pivot selection consistently leads to highly unbalanced partitions (e.g., already sorted or reverse sorted arrays if the last element is always chosen as pivot).
• Space Complexity: O(log N) due to recursive call stack (average case) or O(N) (worst case).
• In-Place: Generally considered an in-place algorithm because it requires minimal additional memory beyond the input array and recursion stack.