| | 1 | #ifdef RCSID |
|---|
| | 2 | static char RCSid[] = |
|---|
| | 3 | "$Header$"; |
|---|
| | 4 | #endif |
|---|
| | 5 | |
|---|
| | 6 | /* |
|---|
| | 7 | * Copyright (c) 2000, 2002 Michael J. Roberts. All Rights Reserved. |
|---|
| | 8 | * |
|---|
| | 9 | * Please see the accompanying license file, LICENSE.TXT, for information |
|---|
| | 10 | * on using and copying this software. |
|---|
| | 11 | */ |
|---|
| | 12 | /* |
|---|
| | 13 | Name |
|---|
| | 14 | vmsort.cpp - T3 VM quicksort implementation |
|---|
| | 15 | Function |
|---|
| | 16 | Implements quicksort. We use our own implementation rather than the |
|---|
| | 17 | standard C library's qsort() routine for two reasons. First, we might |
|---|
| | 18 | want to throw an exception out of the comparison routine, and it is |
|---|
| | 19 | not clear that it is safe to longjmp() past qsort() on every type of |
|---|
| | 20 | machine and every C run-time implementation. Second, the standard C |
|---|
| | 21 | library's qsort() routine doesn't provide any means to pass a context |
|---|
| | 22 | to the comparison callback, and further insists that the data to be |
|---|
| | 23 | sorted be arranged as an array; we provide a higher-level abstraction |
|---|
| | 24 | for the comparison callback. |
|---|
| | 25 | Notes |
|---|
| | 26 | |
|---|
| | 27 | Modified |
|---|
| | 28 | 05/14/00 MJRoberts - Creation |
|---|
| | 29 | */ |
|---|
| | 30 | |
|---|
| | 31 | #include <stdlib.h> |
|---|
| | 32 | #include "t3std.h" |
|---|
| | 33 | #include "vmglob.h" |
|---|
| | 34 | #include "vmsort.h" |
|---|
| | 35 | |
|---|
| | 36 | |
|---|
| | 37 | /* ------------------------------------------------------------------------ */ |
|---|
| | 38 | /* |
|---|
| | 39 | * perform a quicksort |
|---|
| | 40 | */ |
|---|
| | 41 | void CVmQSortData::sort(VMG_ size_t l, size_t r) |
|---|
| | 42 | { |
|---|
| | 43 | /* proceed if we have a non-empty range */ |
|---|
| | 44 | if (r > l) |
|---|
| | 45 | { |
|---|
| | 46 | size_t i, j; |
|---|
| | 47 | size_t v_idx = r; |
|---|
| | 48 | |
|---|
| | 49 | /* start at the ends of the range */ |
|---|
| | 50 | i = l - 1; |
|---|
| | 51 | j = r; |
|---|
| | 52 | |
|---|
| | 53 | /* partition the range */ |
|---|
| | 54 | do |
|---|
| | 55 | { |
|---|
| | 56 | /* find the leftmost element >= the right element */ |
|---|
| | 57 | do |
|---|
| | 58 | { |
|---|
| | 59 | ++i; |
|---|
| | 60 | } while (i != r && compare(vmg_ i, v_idx) < 0); |
|---|
| | 61 | |
|---|
| | 62 | /* find the rightmost element <= the right element */ |
|---|
| | 63 | do |
|---|
| | 64 | { |
|---|
| | 65 | --j; |
|---|
| | 66 | } while (j != l && compare(vmg_ j, v_idx) > 0); |
|---|
| | 67 | |
|---|
| | 68 | /* exchange elements i and j */ |
|---|
| | 69 | exchange(vmg_ i, j); |
|---|
| | 70 | |
|---|
| | 71 | /* if we moved the 'v' element, follow that in the index */ |
|---|
| | 72 | if (v_idx == i) |
|---|
| | 73 | v_idx = j; |
|---|
| | 74 | else if (v_idx == j) |
|---|
| | 75 | v_idx = i; |
|---|
| | 76 | |
|---|
| | 77 | } while (j > i); |
|---|
| | 78 | |
|---|
| | 79 | /* undo the last exchange */ |
|---|
| | 80 | exchange(vmg_ i, j); |
|---|
| | 81 | |
|---|
| | 82 | /* exchange the right value into the pivot point */ |
|---|
| | 83 | exchange(vmg_ i, r); |
|---|
| | 84 | |
|---|
| | 85 | /* recursively sort the subranges */ |
|---|
| | 86 | if (i > l) |
|---|
| | 87 | sort(vmg_ l, i - 1); |
|---|
| | 88 | if (i < r) |
|---|
| | 89 | sort(vmg_ i + 1, r); |
|---|
| | 90 | } |
|---|
| | 91 | } |
|---|
| | 92 | |
|---|
Download diff