OLD | NEW |
(Empty) | |
| 1 /* Copyright (c) 2010 The Chromium OS Authors. All rights reserved. |
| 2 * Use of this source code is governed by a BSD-style license that can be |
| 3 * found in the LICENSE file. |
| 4 */ |
| 5 #include "quick_sort.h" |
| 6 #include <stdint.h> |
| 7 #include "utility.h" |
| 8 |
| 9 /* Make sure we won't overflow the buffer. */ |
| 10 #define SAFE_SIZE(size) \ |
| 11 ((size > MAX_QUICK_SORT_ELEMENT_SIZE) ? MAX_QUICK_SORT_ELEMENT_SIZE : size) |
| 12 |
| 13 /* Swap a and b. Since the type of 'a' and 'b' are unknown, caller must indicate |
| 14 * 'size' bytes. */ |
| 15 void Swap(void *a, void *b, int size) { |
| 16 static uint8_t buffer[MAX_QUICK_SORT_ELEMENT_SIZE]; |
| 17 Memcpy(buffer, a, SAFE_SIZE(size)); |
| 18 Memcpy(a, b, SAFE_SIZE(size)); |
| 19 Memcpy(b, buffer, SAFE_SIZE(size)); |
| 20 } |
| 21 |
| 22 /* Given a pivot and left/right boundary, this function returns a new pivot, |
| 23 * and ensure the elements in the left-side of pivot are preceding elements, |
| 24 * and elements in the right-side of pivot are following elements. */ |
| 25 static int |
| 26 Partition(int (*compare_function)(const void *a, const void *b), |
| 27 void *vp_elements, int size, int left, int right, int pivot) { |
| 28 uint8_t *elements = vp_elements; |
| 29 int i; |
| 30 |
| 31 Swap(&elements[right * size], &elements[pivot * size], size); |
| 32 for (i = left; i < right; ++i) { |
| 33 if (compare_function(&elements[i * size], &elements[right * size])) { |
| 34 Swap(&elements[left * size], &elements[i * size], size); |
| 35 ++left; |
| 36 } |
| 37 } |
| 38 Swap(&elements[left * size], &elements[right * size], size); |
| 39 return left; |
| 40 } |
| 41 |
| 42 /* Given left and right boundary, this function returns a sorted elements in |
| 43 * that range. */ |
| 44 static void |
| 45 RecursiveQuickSort(void *elements, int left, int right, int size, |
| 46 int (*compare_function)(const void *a, const void *b)) { |
| 47 int pivot; |
| 48 |
| 49 if (right <= left) return; |
| 50 pivot = (left + right) / 2; |
| 51 pivot = Partition(compare_function, elements, size, left, right, pivot); |
| 52 RecursiveQuickSort(elements, left, pivot - 1, size, compare_function); |
| 53 RecursiveQuickSort(elements, pivot + 1, right, size, compare_function); |
| 54 } |
| 55 |
| 56 void QuickSort(void *elements, int number_of_elements, int size, |
| 57 int (*compare_function)(const void *a, const void *b)) { |
| 58 RecursiveQuickSort(elements, 0, number_of_elements - 1, size, compare_function
); |
| 59 } |
OLD | NEW |