1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
// quickSort
//
// This public-domain C implementation by Darel Rex Finley.
//
// Modified by Giuseppe Gatta
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
#define QSORT_MAX_LEVELS 300
int beg[QSORT_MAX_LEVELS], end[QSORT_MAX_LEVELS], i=0, L, R, swap ;
char piv[size];
beg[0]=0; end[0]=nmemb;
while (i>=0)
{
L=beg[i]; R=end[i]-1;
if (L<R)
{
memcpy(piv, base + (size * L), size);
while (L<R)
{
while(compar(base + (R*size), piv) > 0 && L<R) R--;
if (L<R)
{
memcpy(base + (size *L), base + (size * R), size);
L++;
}
while(compar(base + (L*size), piv) <= 0 && L<R) L++;
if (L<R)
{
memcpy(base + (size *R), base + (size * L), size);
R--;
}
}
memcpy(base + (size*L), piv, size);
beg[i+1]=L+1;
end[i+1]=end[i];
end[i++]=L;
if (end[i]-beg[i]>end[i-1]-beg[i-1])
{
swap=beg[i]; beg[i]=beg[i-1]; beg[i-1]=swap;
swap=end[i]; end[i]=end[i-1]; end[i-1]=swap;
}
}
else
{
i--;
}
}
}
|
