Created
February 13, 2012 21:20
-
-
Save headius/1820596 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* qs6.c */ | |
/*****************************************************/ | |
/* */ | |
/* qs6 (Quick sort function) */ | |
/* */ | |
/* by Tomoyuki Kawamura 1995.4.21 */ | |
/* kawamura@tokuyama.ac.jp */ | |
/*****************************************************/ | |
typedef struct { char *LL, *RR; } stack_node; /* Stack structure for L,l,R,r */ | |
#define PUSH(ll,rr) do { top->LL = (ll); top->RR = (rr); ++top; } while (0) /* Push L,l,R,r */ | |
#define POP(ll,rr) do { --top; (ll) = top->LL; (rr) = top->RR; } while (0) /* Pop L,l,R,r */ | |
#define med3(a,b,c) ((*cmp)((a),(b),d)<0 ? \ | |
((*cmp)((b),(c),d)<0 ? (b) : ((*cmp)((a),(c),d)<0 ? (c) : (a))) : \ | |
((*cmp)((b),(c),d)>0 ? (b) : ((*cmp)((a),(c),d)<0 ? (a) : (c)))) | |
void | |
ruby_qsort(void* base, const size_t nel, const size_t size, | |
int (*cmp)(const void*, const void*, void*), void *d) | |
{ | |
register char *l, *r, *m; /* l,r:left,right group m:median point */ | |
register int t, eq_l, eq_r; /* eq_l: all items in left group are equal to S */ | |
char *L = base; /* left end of current region */ | |
char *R = (char*)base + size*(nel-1); /* right end of current region */ | |
size_t chklim = 63; /* threshold of ordering element check */ | |
stack_node stack[32], *top = stack; /* 32 is enough for 32bit CPU */ | |
int mmkind; | |
size_t high, low, n; | |
if (nel <= 1) return; /* need not to sort */ | |
mmprepare(base, size); | |
goto start; | |
nxt: | |
if (stack == top) return; /* return if stack is empty */ | |
POP(L,R); | |
for (;;) { | |
start: | |
if (L + size == R) { /* 2 elements */ | |
if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt; | |
} | |
l = L; r = R; | |
n = (r - l + size) / size; /* number of elements */ | |
m = l + size * (n >> 1); /* calculate median value */ | |
if (n >= 60) { | |
register char *m1; | |
register char *m3; | |
if (n >= 200) { | |
n = size*(n>>3); /* number of bytes in splitting 8 */ | |
{ | |
register char *p1 = l + n; | |
register char *p2 = p1 + n; | |
register char *p3 = p2 + n; | |
m1 = med3(p1, p2, p3); | |
p1 = m + n; | |
p2 = p1 + n; | |
p3 = p2 + n; | |
m3 = med3(p1, p2, p3); | |
} | |
} | |
else { | |
n = size*(n>>2); /* number of bytes in splitting 4 */ | |
m1 = l + n; | |
m3 = m + n; | |
} | |
m = med3(m1, m, m3); | |
} | |
if ((t = (*cmp)(l,m,d)) < 0) { /*3-5-?*/ | |
if ((t = (*cmp)(m,r,d)) < 0) { /*3-5-7*/ | |
if (chklim && nel >= chklim) { /* check if already ascending order */ | |
char *p; | |
chklim = 0; | |
for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) > 0) goto fail; | |
goto nxt; | |
} | |
fail: goto loopA; /*3-5-7*/ | |
} | |
if (t > 0) { | |
if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/ | |
mmrot3(r,m,l); goto loopA; /*3-5-2*/ | |
} | |
goto loopB; /*3-5-5*/ | |
} | |
if (t > 0) { /*7-5-?*/ | |
if ((t = (*cmp)(m,r,d)) > 0) { /*7-5-3*/ | |
if (chklim && nel >= chklim) { /* check if already ascending order */ | |
char *p; | |
chklim = 0; | |
for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2; | |
while (l<r) {mmswap(l,r); l+=size; r-=size;} /* reverse region */ | |
goto nxt; | |
} | |
fail2: mmswap(l,r); goto loopA; /*7-5-3*/ | |
} | |
if (t < 0) { | |
if ((*cmp)(l,r,d) <= 0) {mmswap(l,m); goto loopB;} /*7-5-8*/ | |
mmrot3(l,m,r); goto loopA; /*7-5-6*/ | |
} | |
mmswap(l,r); goto loopA; /*7-5-5*/ | |
} | |
if ((t = (*cmp)(m,r,d)) < 0) {goto loopA;} /*5-5-7*/ | |
if (t > 0) {mmswap(l,r); goto loopB;} /*5-5-3*/ | |
/* determining splitting type in case 5-5-5 */ /*5-5-5*/ | |
for (;;) { | |
if ((l += size) == r) goto nxt; /*5-5-5*/ | |
if (l == m) continue; | |
if ((t = (*cmp)(l,m,d)) > 0) {mmswap(l,r); l = L; goto loopA;}/*575-5*/ | |
if (t < 0) {mmswap(L,l); l = L; goto loopB;} /*535-5*/ | |
} | |
loopA: eq_l = 1; eq_r = 1; /* splitting type A */ /* left <= median < right */ | |
for (;;) { | |
for (;;) { | |
if ((l += size) == r) | |
{l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;} | |
if (l == m) continue; | |
if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;} | |
if (t < 0) eq_l = 0; | |
} | |
for (;;) { | |
if (l == (r -= size)) | |
{l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;} | |
if (r == m) {m = l; break;} | |
if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;} | |
if (t == 0) break; | |
} | |
mmswap(l,r); /* swap left and right */ | |
} | |
loopB: eq_l = 1; eq_r = 1; /* splitting type B */ /* left < median <= right */ | |
for (;;) { | |
for (;;) { | |
if (l == (r -= size)) | |
{r += size; if (r != m) mmswap(r,m); r += size; goto fin;} | |
if (r == m) continue; | |
if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;} | |
if (t > 0) eq_r = 0; | |
} | |
for (;;) { | |
if ((l += size) == r) | |
{r += size; if (r != m) mmswap(r,m); r += size; goto fin;} | |
if (l == m) {m = r; break;} | |
if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;} | |
if (t == 0) break; | |
} | |
mmswap(l,r); /* swap left and right */ | |
} | |
fin: | |
if (eq_l == 0) /* need to sort left side */ | |
if (eq_r == 0) /* need to sort right side */ | |
if (l-L < R-r) {PUSH(r,R); R = l;} /* sort left side first */ | |
else {PUSH(L,l); L = r;} /* sort right side first */ | |
else R = l; /* need to sort left side only */ | |
else if (eq_r == 0) L = r; /* need to sort right side only */ | |
else goto nxt; /* need not to sort both sides */ | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment