1 /*
2 * sort.c - Sample ELF module providing a quick sort function
3 *
4 * Created on: Aug 11, 2008
5 * Author: Stefan Bucur <stefanb@zytor.com>
6 */
7
8 #include <stdlib.h>
9
swap(int * x,int * y)10 static inline void swap(int *x, int *y)
11 {
12 int tmp;
13 tmp = *x;
14 *x = *y;
15 *y = tmp;
16 }
17
randint(int l,int u)18 static inline int randint(int l, int u)
19 {
20 return l + (rand() % (u - l + 1));
21 }
22
23 /**
24 * quick_sort_range - A small and efficient version of quicksort.
25 * @nums: The numbers to sort
26 * @l: The lower index in the vector (inclusive)
27 * @u: The upper index in the vector (inclusive)
28 *
29 * The implementation is taken from "Beautiful Code", by O'Reilly, the
30 * book students received from Google as a gift for their acceptance
31 * in the GSoC 2008 program. The code belongs to Jon Bentley, who
32 * wrote the third chapter of the book. Since ELF modules were written
33 * as part of this program, the author of the module considered
34 * the book had to be put to some use. :)
35 */
quick_sort_range(int * nums,int l,int u)36 static void quick_sort_range(int *nums, int l, int u)
37 {
38 int i, m;
39 if (l >= u)
40 return;
41
42 swap(&nums[l], &nums[randint(l, u)]);
43
44 m = l;
45 for (i = l + 1; i <= u; i++) {
46 if (nums[i] < nums[l])
47 swap(&nums[++m], &nums[i]);
48 }
49
50 swap(&nums[l], &nums[m]);
51
52 quick_sort_range(nums, l, m - 1);
53 quick_sort_range(nums, m + 1, u);
54 }
55
quick_sort(int * nums,int count)56 void quick_sort(int *nums, int count)
57 {
58 quick_sort_range(nums, 0, count - 1);
59 }
60