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;
}