The canonical example for Quick Sort

Quick Sort.md

Quick Sort

Notes here

quicksort.c

#include <stdlib.h> #For rand

int partition(int *arr, int pivot, int size) {
    int i=1, temp=arr[pivot];

    arr[pivot] = arr[0];
    arr[0] = temp;

    for (int j=1; j < size; j++)
        if (arr[j] < arr[0]) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }

    temp = arr[0];
    arr[0] = arr[i-1];
    arr[i-1] = temp;

    return i-1;
}

void quickSort(int *arr, int size) {
    if (size < 2)
        return;

    int pivot = rand() % size; //Crux of quick sort - choosing a random pivot
    pivot = partition(arr, pivot, size);
    quickSort(arr, pivot);
    quickSort(arr+pivot+1, size-pivot-1);
}

quicksort.cpp

using namespace std;

#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <iostream>

vector<int>::iterator partition(vector<int>::iterator p, vector<int>::iterator st, vector<int>::iterator en) {
    iter_swap(st, p);
    auto i=st+1, j=st+1;
    while (j != en && *j <= *st) j++;
    i = j;
    for (; j != en; j++) {
        if (*j <= *st) {
            iter_swap(i, j);
            i++;
        }
    }
    iter_swap(st, i-1);
    return i-1;
}

// Normal - but it can be converted to tail recursive (normally done by the compiler)
void quickSort(vector<int>::iterator st, vector<int>::iterator en) {
    uint32_t dist = (en - st);
    if (dist <= 1) return;

    auto rp = st  + (rand() % dist);
    rp = partition(rp, st, en);
    quickSort(st, rp);
    quickSort(rp+1, en);
}

// Tail recursion elimination
void quickSortTR(vector<int>::iterator st, vector<int>::iterator en) {
    while (st < en) {
        uint32_t dist = (en-st);
        if (dist <= 1) return;
        auto rp = st + (rand() % dist);
        rp = partition(rp, st, en);
        quickSortTR(st, rp);
        st=rp+1;
    }
}

int main() {

    int arr[] = {5,18,56,34,2,34,55,23,463,435,4,334,79,7,9};
    ///int arr[] = {7,6,34,8,34,56,23};
    vector<int> vec(arr, arr + sizeof(arr) / sizeof(arr[0]));

    for (auto num : vec) cout << num << " ";
    cout << endl;

    quickSortTR(vec.begin(), vec.end());
    cout << endl;

    for (auto num : vec) cout << num << " ";
    cout << endl;

    return 0;
}