-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort.c
83 lines (49 loc) · 2.11 KB
/
sort.c
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
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <fcntl.h>
#include <alloca.h>
#include <limits.h>
#include <string.h>
#include "sort.h"
/* Byte-wise swap two items of size SIZE. */
#define SWAP(a, b, size) \
do \
{ \
size_t __size = (size); \
char *__a = (a), *__b = (b); \
do \
{ \
char __tmp = *__a; \
*__a++ = *__b; \
*__b++ = __tmp; \
} while (--__size > 0); \
} while (0)
static void fastsort(char* low, char* hight,size_t size, __compar_d_fn_t cmp, void *arg)
{
if ( low < hight )
{
char *lo = low; char *hi = hight;
char* mid = lo + size * ( (hi - lo) / size >> 1 );
do {
while ( (*cmp) ( (void*)mid, (void*)lo, arg) > 0)
lo += size;
while ( (*cmp) ( (void*)hi,(void*)mid, arg) > 0)
hi -= size;
if (lo <= hi) {
SWAP (lo,hi,size);
lo +=size;
hi -=size;
}
} while (lo <= hi);
if (hi>low) fastsort(low, hi, size, cmp, arg);
if (hight>lo) fastsort(lo, hight, size, cmp, arg);
}
}
void quicksort(void *const pbase, size_t total_elems, size_t size,
__compar_d_fn_t cmp, void *arg)
{
char * low = (char*)pbase;
char * hight = &low[size * (total_elems - 1)];
fastsort(low,hight,size,cmp,arg);
}