aboutsummaryrefslogtreecommitdiffstats
path: root/sort.c
blob: f3fb570896ee6754ca8baf36528c1ddaefb6d178 (plain)
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
/*
 * sort.c
 * implementation of different sorting algorithms
 *
 * Erik Liodden
 */

#include <stddef.h>
#include <string.h>
#include "misc.h"


void insertion_sort(void *base, size_t nel, size_t width,
		int (*compar)(const void *, const void *))
{
	int j, i;

	for (j = 1; j < (int)nel; j++) {
		for (i = j-1; i >= 0 && compar((char *)base+i*width,
					(char *)base+j*width) > 0; i--)
			;
		rotate((char *)base + (i+1)*width, (char *)base +j*width,
				(char *)base +(j+1)*width);
	}
}

static int partition(void *base, int p, int r, size_t width,
		int (*compar)(const void *, const void *))
{
	int i, j;
	void *x = allocate(width);
	memcpy(x, (char *)base + r*width, width);
	i = p-1;
	for (j = p; j <= r-1; j++) {
		if (compar((char *)base + j*width, x) <= 0) {
			i = i+1;
			swap((char *)base +i*width, (char *)base +j*width, width);
		}
	}
	swap((char *)base + (i+1)*width, (char *)base + r*width, width);
	return i+1;
}

static void q_sort(void *base, int p, int r, size_t width,
		int (*compar)(const void *, const void *))
{
	int q;
	if (p < r) {
		q = partition(base, p, r, width, compar);
		q_sort(base, p, q-1, width, compar);
		q_sort(base, q+1, r, width, compar);
	}
}

void quick_sort(void *base, size_t nel, size_t width,
		int (*compar)(const void *, const void *))
{
	q_sort(base, 0, (int)nel-1, width, compar);
}