Simple Sorting Algorithms with C++

Welcome to the lesson dedicated to Quick Sort. Sorting is one of the most investigated classes of algorithms in computer science. Understanding different methods of sorting becomes more crucial as data sizes increase.

The QuickSort algorithm is designed to sort an unsorted array by employing the Divide and Conquer Technique. The algorithm efficiently achieves this with an average time complexity of O(n log n). The idea behind it is to pick a pivot element from the array and partition the other elements into two arrays according to whether they are less than or greater than the pivot.

Here's an overview of how QuickSort works:

1. Pivot Selection: Choose a pivot element from the array.

   • The pivot can be any element, but commonly used strategies include picking the first element, the last element, or selecting a random element.

2. Partitioning the Array: Rearrange the array such that:

   • All elements less than the pivot come before the pivot.
   • All elements greater than the pivot come after the pivot.
   • The pivot element is now in its correct sorted position.

3. Recursive Sorting:

   • Recursively apply the quickSort function to the subarray of elements with values less than the pivot.
   • Recursively apply the quickSort function to the subarray of elements with values greater than the pivot.

Given the array [10, 7, 8, 9, 1, 5], let's sort it using QuickSort:

1. Choose Pivot: Let's pick the last element, 5, as the pivot.

2. Partition:

   • Elements less than 5: [1]
   • Elements greater than 5: [10, 7, 8, 9]
   • Array after partitioning: [1, 5, 10, 7, 8, 9]

3. Recursive QuickSort:

   • Apply QuickSort to [1] (Already sorted)
   • Apply QuickSort to [10, 7, 8, 9]

4. Repeat the process for the subarray [10, 7, 8, 9], choosing pivots, partitioning, and recursing until the entire array is sorted.

This approach ensures that the sorting process is performed efficiently by continually breaking down the problem into smaller subproblems, which are easier to solve.

We will use a helper function: partition.

The implementation of QuickSort is:

#include <iostream>
#include <vector>
#include <algorithm>

// Partition function that makes use 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; j++) {
        // If the current element is smaller than or equal to the pivot
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// The main function that implements QuickSort
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // pi is the partitioning index, arr[p] is now at the 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);
    }
}