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 | |
---|