]>
Commit | Line | Data |
---|---|---|
e0edde6f | 1 | /* Copyright (c) 2009 Nicira, Inc. |
f85f8ebb BP |
2 | * |
3 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
4 | * you may not use this file except in compliance with the License. | |
5 | * You may obtain a copy of the License at: | |
6 | * | |
7 | * http://www.apache.org/licenses/LICENSE-2.0 | |
8 | * | |
9 | * Unless required by applicable law or agreed to in writing, software | |
10 | * distributed under the License is distributed on an "AS IS" BASIS, | |
11 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
12 | * See the License for the specific language governing permissions and | |
13 | * limitations under the License. | |
14 | */ | |
15 | ||
16 | #include <config.h> | |
17 | ||
18 | #include "sort.h" | |
19 | ||
20 | #include "random.h" | |
21 | ||
22 | static size_t | |
23 | partition(size_t p, size_t r, | |
24 | int (*compare)(size_t a, size_t b, void *aux), | |
25 | void (*swap)(size_t a, size_t b, void *aux), | |
26 | void *aux) | |
27 | { | |
28 | size_t x = r - 1; | |
29 | size_t i, j; | |
30 | ||
31 | i = p; | |
32 | for (j = p; j < x; j++) { | |
33 | if (compare(j, x, aux) <= 0) { | |
34 | swap(i++, j, aux); | |
35 | } | |
36 | } | |
37 | swap(i, x, aux); | |
38 | return i; | |
39 | } | |
40 | ||
41 | static void | |
42 | quicksort(size_t p, size_t r, | |
43 | int (*compare)(size_t a, size_t b, void *aux), | |
44 | void (*swap)(size_t a, size_t b, void *aux), | |
45 | void *aux) | |
46 | { | |
47 | size_t i, q; | |
48 | ||
49 | if (r - p < 2) { | |
50 | return; | |
51 | } | |
52 | ||
53 | i = random_range(r - p) + p; | |
54 | if (r - 1 != i) { | |
55 | swap(r - 1, i, aux); | |
56 | } | |
57 | ||
58 | q = partition(p, r, compare, swap, aux); | |
59 | quicksort(p, q, compare, swap, aux); | |
60 | quicksort(q, r, compare, swap, aux); | |
61 | } | |
62 | ||
63 | void | |
64 | sort(size_t count, | |
65 | int (*compare)(size_t a, size_t b, void *aux), | |
66 | void (*swap)(size_t a, size_t b, void *aux), | |
67 | void *aux) | |
68 | { | |
69 | quicksort(0, count, compare, swap, aux); | |
70 | } |