Quick Sort

#include <iostream>
using namespace std;

// Function to partition the array
int partition(int arr[], int s, int e) {
    int pivot = arr[s]; // Choosing the first element as the pivot
    int cnt = 0; // Count elements smaller than pivot

    // Count how many elements are less than or equal to pivot
    for (int i = s + 1; i <= e; i++) {
        if (arr[i] <= pivot) {
            cnt++;
        }
    }

    // Finding the correct index for the pivot
    int pivotIndex = s + cnt;
    swap(arr[pivotIndex], arr[s]); // Placing pivot at its correct position

    // Sorting left and right parts around the pivot
    int i = s, j = e;

    while (i < pivotIndex && j > pivotIndex) {
        // Move 'i' forward if it's less than or equal to pivot
        while (arr[i] <= pivot) {
            i++;
        }

        // Move 'j' backward if it's greater than pivot
        while (arr[j] > pivot) {
            j--;
        }

        // Swap elements if they are on the wrong side of pivot
        if (i < pivotIndex && j > pivotIndex) {
            swap(arr[i++], arr[j--]);
        }
    }

    return pivotIndex; // Return the index of the pivot
}

// Function to perform Quick Sort
void quickSort(int arr[], int s, int e) {
    // Base case: if there's only one or no element, return
    if (s >= e) {
        return;
    }

    // Partition the array and get the pivot index
    int p = partition(arr, s, e);

    // Recursively sort the left subarray
    quickSort(arr, s, p - 1);

    // Recursively sort the right subarray
    quickSort(arr, p + 1, e);
}

int main() {
    int arr[10] = {2, 4, 1, 6, 9, 9, 9, 9, 9, 9}; // Sample array
    int n = 10; // Size of the array

    // Perform Quick Sort
    quickSort(arr, 0, n - 1);

    // Print the sorted array
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Example Walkthrough:

Input Array

[2, 4, 1, 6, 9, 9, 9, 9, 9, 9]

• Select a Pivot (First element of the array)

Pivot = 2
Count elements ≤ pivot: 0

• Recursive Sorting

Left Partition: []  (Nothing to sort)
Right Partition: [4, 1, 6, 9, 9, 9, 9, 9, 9]

• Repeat for Right Partition

Pivot = 4
Count elements ≤ pivot: 1
Swap pivot with correct position.

• Final Sorted Array:

[1, 2, 4, 6, 9, 9, 9, 9, 9, 9]