Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <stdint.h>
void swap2(int* first, int* second)
{
int temp = *first;
*first = *second;
*second = temp;
}
// min max
int min(int a,int b)
{
return a < b ? a : b;
}
int max(int a,int b)
{
return a > b ? a : b;
}
// median of 3
int median3(int a, int b, int c)
{
int median = max(min(a,b), min(max(a,b),c));
return median;
}
/////////////////////////
typedef int CMPFUNC (const void *a, const void *b);
int cmp(const void* a, const void* b)
{
int arg1 = *(const int*)a;
int arg2 = *(const int*)b;
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
}
//#define cmp(a,b) (*(a) > *(b))
#define parity_merge_two(array, swap, x, y, ptl, ptr, pts, cmp) \
{ \
ptl = array + 0; ptr = array + 2; pts = swap + 0; \
x = cmp(ptl, ptr) <= 0; y = !x; pts[x] = *ptr; ptr += y; pts[y] = *ptl; ptl += x; pts++; \
*pts = cmp(ptl, ptr) <= 0 ? *ptl : *ptr; \
\
ptl = array + 1; ptr = array + 3; pts = swap + 3; \
x = cmp(ptl, ptr) <= 0; y = !x; pts--; pts[x] = *ptr; ptr -= x; pts[y] = *ptl; ptl -= y; \
*pts = cmp(ptl, ptr) > 0 ? *ptl : *ptr; \
}
#define parity_merge_four(array, swap, x, y, ptl, ptr, pts, cmp) \
{ \
ptl = array + 0; ptr = array + 4; pts = swap; \
x = cmp(ptl, ptr) <= 0; y = !x; pts[x] = *ptr; ptr += y; pts[y] = *ptl; ptl += x; pts++; \
x = cmp(ptl, ptr) <= 0; y = !x; pts[x] = *ptr; ptr += y; pts[y] = *ptl; ptl += x; pts++; \
x = cmp(ptl, ptr) <= 0; y = !x; pts[x] = *ptr; ptr += y; pts[y] = *ptl; ptl += x; pts++; \
*pts = cmp(ptl, ptr) <= 0 ? *ptl : *ptr; \
\
ptl = array + 3; ptr = array + 7; pts = swap + 7; \
x = cmp(ptl, ptr) <= 0; y = !x; pts--; pts[x] = *ptr; ptr -= x; pts[y] = *ptl; ptl -= y; \
x = cmp(ptl, ptr) <= 0; y = !x; pts--; pts[x] = *ptr; ptr -= x; pts[y] = *ptl; ptl -= y; \
x = cmp(ptl, ptr) <= 0; y = !x; pts--; pts[x] = *ptr; ptr -= x; pts[y] = *ptl; ptl -= y; \
*pts = cmp(ptl, ptr) > 0 ? *ptl : *ptr; \
}
void parity_swap_four32(int *array, CMPFUNC *cmp)
{
int swap[4], *ptl, *ptr, *pts;
unsigned char x, y;
x = cmp(array + 0, array + 1) <= 0; y = !x; swap[0 + y] = array[0]; swap[0 + x] = array[1];
x = cmp(array + 2, array + 3) <= 0; y = !x; swap[2 + y] = array[2]; swap[2 + x] = array[3];
parity_merge_two(swap, array, x, y, ptl, ptr, pts, cmp);
}
void parity_swap_eight32(int *array, CMPFUNC *cmp)
{
int swap[8], *ptl, *ptr, *pts;
unsigned char x, y;
if (cmp(array + 0, array + 1) > 0) { swap[0] = array[0]; array[0] = array[1]; array[1] = swap[0]; }
if (cmp(array + 2, array + 3) > 0) { swap[0] = array[2]; array[2] = array[3]; array[3] = swap[0]; }
if (cmp(array + 4, array + 5) > 0) { swap[0] = array[4]; array[4] = array[5]; array[5] = swap[0]; }
if (cmp(array + 6, array + 7) > 0) { swap[0] = array[6]; array[6] = array[7]; array[7] = swap[0]; } else
if (cmp(array + 1, array + 2) <= 0 && cmp(array + 3, array + 4) <= 0 && cmp(array + 5, array + 6) <= 0)
{
return;
}
parity_merge_two(array + 0, swap + 0, x, y, ptl, ptr, pts, cmp);
parity_merge_two(array + 4, swap + 4, x, y, ptl, ptr, pts, cmp);
parity_merge_four(swap, array, x, y, ptl, ptr, pts, cmp);
}
void unguarded_insert32(int *array, size_t offset, size_t nmemb, CMPFUNC *cmp)
{
int key, *pta, *end;
size_t i, top;
for (i = offset ; i < nmemb ; i++)
{
pta = end = array + i;
if (cmp(--pta, end) <= 0)
{
continue;
}
key = *end;
if (cmp(array, &key) > 0)
{
top = i;
do
{
*end-- = *pta--;
}
while (--top);
*end = key;
}
else
{
do
{
*end-- = *pta--;
}
while (cmp(pta, &key) > 0);
*end = key;
}
}
}
#define MAG_LEN 10
void quicksort2(int *A, int len) {
if (len < 2) return;
if(len==2)
{
if(A[0]>A[1])
swap2(&A[0],&A[1]);
return;
}
else if(len==3)
{
unguarded_insert32(A, 1, len, cmp);
return;
}
else if(len<8 )
{
parity_swap_four32(A,cmp);
unguarded_insert32(A,4,len,cmp);
return;
}
else if(len<16 )
{
parity_swap_eight32(A,cmp);
unguarded_insert32(A,4,len,cmp);
return;
}
int pivot;
if(len<MAG_LEN)
pivot = A[len / 2];
else
pivot=median3(A[0],A[len/2],A[len-1]);
int i, j;
for (i = 0, j = len - 1; ; i++, j--) {
while (A[i] < pivot) i++;
while (A[j] > pivot) j--;
if (i >= j) break;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
quicksort2(A, i);
quicksort2(A + i, len - i);
}