C++ implementation of quick sort.

Cover image by Andre Taissin on Unsplash.

Table of Contents

Quick sort

#include <stdio.h>

#define SWAP(a,b) (((a)==(b)) || ((a)^=(b), (b)^=(a), (a)^=(b)))

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

void qsort(int *first, int *last, bool (*cmp)(const int*, const int*)){
    if(first >= last) return;

    int *mid = first + ((last - first) >> 1);
    int pivot = *mid;
    int *last1 = last - 1;
    swap(mid, last1);
    // SWAP(*mid, *last1);

    int *first_cmp_false = first;
    for(int *p = first; p < last1; ++p)
        if(cmp(p, &pivot)){
            swap(p, first_cmp_false);
            // SWAP(*p, *first_cmp_false);
            ++first_cmp_false;
        }
    swap(first_cmp_false, last1);
    // SWAP(*first_cmp_false, *last1);

    qsort(first, first_cmp_false, cmp);
    qsort(first_cmp_false+1, last, cmp);
}

bool less(const int *a, const int *b){ return *a < *b; }
bool greater(const int *a, const int *b){ return *a > *b; }
bool less_equal(const int *a, const int *b){ return *a < *b; }

int main(){
    int n;
    int a[101];

    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    
    qsort(a, a+n, &less);
    // qsort(a, a+n, &greater);
    // qsort(a, a+n, &less_equal);

    for(int i = 0; i < n; ++i)
        printf("%d ", a[i]);
    putchar('\n');

    return 0;
}