C++ Program to Implement Quick Sort

Quick Sort is a highly efficient and widely used sorting algorithm developed by Tony Hoare in 1959. It employs a divide-and-conquer strategy to sort elements. This article will guide you through the implementation of Quick Sort in C++, providing detailed explanations and multiple examples to illustrate its application.

Prerequisites

Before diving into the implementation, ensure you have a basic understanding of the following concepts:

  1. Arrays: A collection of elements stored at contiguous memory locations.
  2. C++ Syntax: Basic knowledge of C++ programming, including loops, conditional statements, and functions.
  3. Recursion: Understanding how recursive functions work, as Quick Sort is often implemented using recursion.

1. Introduction to Quick Sort

1.1 Definition

Quick Sort is an efficient, comparison-based, in-place sorting algorithm. 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.

1.2 Algorithm Steps

  1. Choose a Pivot: Select an element from the array as the pivot.
  2. Partitioning: Rearrange the array so that all elements less than the pivot are on the left, and all elements greater than the pivot are on the right.
  3. Recursively Apply: Apply the above steps recursively to the sub-arrays of elements with smaller and greater values.

2. Implementation of Quick Sort in C++

2.1 Example 1: Basic Quick Sort

Let’s start with a basic implementation of Quick Sort in C++.

C++
#include <iostream>
using namespace std;

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // pivot
    int i = (low - 1);  // Index of smaller element
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Output:

C++
Sorted array: 1 5 7 8 9 10

2.2 Example 2: Quick Sort with Different Pivot Selection

Choosing a pivot is crucial for the efficiency of Quick Sort. Here, we implement Quick Sort with the pivot being the middle element.

C++
#include <iostream>
using namespace std;

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    int pivot = arr[mid];  // pivot as middle element
    swap(&arr[mid], &arr[high]);  // move pivot to end
    int i = (low - 1);
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {24, 97, 40, 67, 88, 85, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Output:

C++
Sorted array: 15 24 40 67 85 88 97

2.3 Example 3: Quick Sort with Strings

Quick Sort can also be applied to an array of strings. This example demonstrates sorting an array of strings in lexicographical order.

C++
#include <iostream>
#include <string>
using namespace std;

void swap(string* a, string* b) {
    string t = *a;
    *a = *b;
    *b = t;
}

int partition(string arr[], int low, int high) {
    string pivot = arr[high];  // pivot
    int i = (low - 1);
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(string arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(string arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    string arr[] = {"apple", "orange", "banana", "grape", "cherry"};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Output:

C++
Sorted array: apple banana cherry grape orange

Conclusion

Quick Sort is a powerful sorting algorithm that excels in performance with an average-case time complexity of O(n log n). This article provided a comprehensive guide to implementing Quick Sort in C++, demonstrating the algorithm’s versatility through examples with integers and strings, and showcasing different pivot selection strategies