[1] | 1 | typedef cmt_string T; |
---|
| 2 | |
---|
| 3 | typedef T* RandomAccessIterator; |
---|
| 4 | typedef T* BidirectionalIterator1; |
---|
| 5 | typedef T* BidirectionalIterator2; |
---|
| 6 | typedef T* ForwardIterator1; |
---|
| 7 | typedef T* ForwardIterator2; |
---|
| 8 | |
---|
| 9 | //template <class ForwardIterator1, class ForwardIterator2, class T> |
---|
| 10 | void iter_swap (ForwardIterator1 a, ForwardIterator2 b, T*) |
---|
| 11 | { |
---|
| 12 | T tmp = *a; |
---|
| 13 | *a = *b; |
---|
| 14 | *b = tmp; |
---|
| 15 | } |
---|
| 16 | |
---|
| 17 | //template <class RandomAccessIterator, class T> |
---|
| 18 | RandomAccessIterator unguarded_partition (RandomAccessIterator first, |
---|
| 19 | RandomAccessIterator last, |
---|
| 20 | T pivot) |
---|
| 21 | { |
---|
| 22 | while (true) |
---|
| 23 | { |
---|
| 24 | while (*first < pivot) ++first; |
---|
| 25 | --last; |
---|
| 26 | while (pivot < *last) --last; |
---|
| 27 | |
---|
| 28 | if (!(first < last)) return first; |
---|
| 29 | |
---|
| 30 | iter_swap (first, last, first); |
---|
| 31 | |
---|
| 32 | ++first; |
---|
| 33 | } |
---|
| 34 | } |
---|
| 35 | |
---|
| 36 | //template <class T> |
---|
| 37 | const T& median (const T& a, const T& b, const T& c) |
---|
| 38 | { |
---|
| 39 | if (a < b) |
---|
| 40 | if (b < c) |
---|
| 41 | return b; |
---|
| 42 | else if (a < c) |
---|
| 43 | return c; |
---|
| 44 | else |
---|
| 45 | return a; |
---|
| 46 | else if (a < c) |
---|
| 47 | return a; |
---|
| 48 | else if (b < c) |
---|
| 49 | return c; |
---|
| 50 | else |
---|
| 51 | return b; |
---|
| 52 | } |
---|
| 53 | |
---|
| 54 | const int threshold = 16; |
---|
| 55 | |
---|
| 56 | //template <class RandomAccessIterator, class T> |
---|
| 57 | void quick_sort_loop (RandomAccessIterator first, |
---|
| 58 | RandomAccessIterator last, T* t) |
---|
| 59 | { |
---|
| 60 | while ((last - first) > threshold) |
---|
| 61 | { |
---|
| 62 | RandomAccessIterator cut = unguarded_partition |
---|
| 63 | (first, |
---|
| 64 | last, |
---|
| 65 | T (median(*first, |
---|
| 66 | *(first + (last - first)/2), |
---|
| 67 | *(last - 1)))); |
---|
| 68 | |
---|
| 69 | T pivot = median(*first, |
---|
| 70 | *(first + (last - first)/2), |
---|
| 71 | *(last - 1)); |
---|
| 72 | |
---|
| 73 | if (cut - first >= last - cut) |
---|
| 74 | { |
---|
| 75 | quick_sort_loop (cut, last, t); |
---|
| 76 | last = cut; |
---|
| 77 | } |
---|
| 78 | else |
---|
| 79 | { |
---|
| 80 | quick_sort_loop (first, cut, t); |
---|
| 81 | first = cut; |
---|
| 82 | } |
---|
| 83 | } |
---|
| 84 | } |
---|
| 85 | |
---|
| 86 | //template <class RandomAccessIterator, class T> |
---|
| 87 | void unguarded_linear_insert (RandomAccessIterator last, T value) |
---|
| 88 | { |
---|
| 89 | RandomAccessIterator next = last; |
---|
| 90 | --next; |
---|
| 91 | while (value < *next) |
---|
| 92 | { |
---|
| 93 | *last = *next; |
---|
| 94 | last = next--; |
---|
| 95 | } |
---|
| 96 | *last = value; |
---|
| 97 | } |
---|
| 98 | |
---|
| 99 | //template <class BidirectionalIterator1, class BidirectionalIterator2> |
---|
| 100 | BidirectionalIterator2 copy_backward (BidirectionalIterator1 first, |
---|
| 101 | BidirectionalIterator1 last, |
---|
| 102 | BidirectionalIterator2 result) |
---|
| 103 | { |
---|
| 104 | while (first != last) *--result = *--last; |
---|
| 105 | return result; |
---|
| 106 | } |
---|
| 107 | |
---|
| 108 | //template <class RandomAccessIterator, class T> |
---|
| 109 | void linear_insert (RandomAccessIterator first, |
---|
| 110 | RandomAccessIterator last, T*) |
---|
| 111 | { |
---|
| 112 | T value = *last; |
---|
| 113 | if (value < *first) |
---|
| 114 | { |
---|
| 115 | copy_backward(first, last, last + 1); |
---|
| 116 | *first = value; |
---|
| 117 | } |
---|
| 118 | else |
---|
| 119 | unguarded_linear_insert (last, value); |
---|
| 120 | } |
---|
| 121 | |
---|
| 122 | //template <class RandomAccessIterator> |
---|
| 123 | void insertion_sort (RandomAccessIterator first, RandomAccessIterator last) |
---|
| 124 | { |
---|
| 125 | if (!(first == last)) |
---|
| 126 | for (RandomAccessIterator i = first + 1; i != last; ++i) |
---|
| 127 | linear_insert(first, i, first); |
---|
| 128 | } |
---|
| 129 | |
---|
| 130 | //template <class RandomAccessIterator, class T> |
---|
| 131 | void unguarded_insertion_sort (RandomAccessIterator first, |
---|
| 132 | RandomAccessIterator last, T*) |
---|
| 133 | { |
---|
| 134 | for (RandomAccessIterator i = first; i != last; ++i) |
---|
| 135 | unguarded_linear_insert (i, T(*i)); |
---|
| 136 | } |
---|
| 137 | |
---|
| 138 | //template <class RandomAccessIterator> |
---|
| 139 | void final_insertion_sort (RandomAccessIterator first, |
---|
| 140 | RandomAccessIterator last) |
---|
| 141 | { |
---|
| 142 | if (last - first > threshold) |
---|
| 143 | { |
---|
| 144 | insertion_sort (first, first + threshold); |
---|
| 145 | unguarded_insertion_sort (first + threshold, last, first); |
---|
| 146 | } |
---|
| 147 | else |
---|
| 148 | insertion_sort (first, last); |
---|
| 149 | } |
---|
| 150 | |
---|
| 151 | //template <class RandomAccessIterator> |
---|
| 152 | void sort (RandomAccessIterator first, |
---|
| 153 | RandomAccessIterator last) |
---|
| 154 | { |
---|
| 155 | if (!(first == last)) |
---|
| 156 | { |
---|
| 157 | quick_sort_loop (first, last, first); |
---|
| 158 | final_insertion_sort (first, last); |
---|
| 159 | } |
---|
| 160 | } |
---|
| 161 | |
---|