Greg Hartman | 76d05dc | 2016-11-23 15:51:27 -0800 | [diff] [blame] | 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 | |
| 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 | } |