1 /* 2 * sort.c - Sample ELF module providing a quick sort function 3 * 4 * Created on: Aug 11, 2008 5 * Author: Stefan Bucur <stefanb (at) zytor.com> 6 */ 7 8 #include <stdlib.h> 9 10 static inline void swap(int *x, int *y) 11 { 12 int tmp; 13 tmp = *x; 14 *x = *y; 15 *y = tmp; 16 } 17 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 */ 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 56 void quick_sort(int *nums, int count) 57 { 58 quick_sort_range(nums, 0, count - 1); 59 } 60
