Quick Sort Algorithm in CPP

1. Introduction

Quick Sort is a divide-and-conquer algorithm which 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 recursively sorted.

2. Implementation Steps

1. Choose a 'pivot' element from the array.

2. Partition the array around the pivot, such that elements smaller than the pivot come before it and elements greater come after.

3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

3. Implementation in C++ Programming

#include<iostream>
#include<vector>
// Function to swap two numbers
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
// This function takes last element as pivot, places the pivot element at its correct position
// in sorted array, and places all smaller (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
    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);
}
// Function to perform quick sort
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);  // Recursively sort the elements before partition
        quickSort(arr, pi + 1, high);  // Recursively sort the elements after partition
    }
}
int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quickSort(arr, 0, n - 1);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output:

Sorted array:
1 5 7 8 9 10

Explanation:

1. The essence of Quick Sort is in the partitioning. It takes the last element as the pivot and places it at its correct position in the sorted array. All smaller elements are moved to its left, and all larger elements to its right.

2. Once the pivot is in its correct position, the array is divided into two halves. The left half (elements smaller than the pivot) and the right half (elements greater than the pivot) are then recursively sorted using the same partitioning method.

3. This process continues, creating smaller and smaller partitions until the base case is reached where a partition has less than two elements. At that point, it is considered sorted.

4. The efficiency of Quick Sort arises from the fact that, on average, each element only needs to be compared about log(n) times before it's in its final position.