| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 /** | |
| 6 * Dual-Pivot Quicksort algorithm. | |
| 7 * | |
| 8 * This class implements the dual-pivot quicksort algorithm as presented in | |
| 9 * Vladimir Yaroslavskiy's paper. | |
| 10 * | |
| 11 * Some improvements have been copied from Android's implementation. | |
| 12 */ | |
| 13 class DualPivotQuicksort { | |
| 14 // When a list has less then [:_INSERTION_SORT_THRESHOLD:] elements it will | |
| 15 // be sorted by an insertion sort. | |
| 16 static const int _INSERTION_SORT_THRESHOLD = 32; | |
| 17 | |
| 18 /** | |
| 19 * Sorts all elements of the given list [:a:] according to the given | |
| 20 * [:compare:] function. | |
| 21 * | |
| 22 * The [:compare:] function takes two arguments [:x:] and [:y:] and returns | |
| 23 * -1 if [:x < y:], | |
| 24 * 0 if [:x == y:], and | |
| 25 * 1 if [:x > y:]. | |
| 26 * | |
| 27 * The function's behavior must be consistent. It must not return different | |
| 28 * results for the same values. | |
| 29 */ | |
| 30 static void sort(List a, int compare(a, b)) { | |
| 31 _doSort(a, 0, a.length - 1, compare); | |
| 32 } | |
| 33 | |
| 34 /** | |
| 35 * Sorts all elements in the range [:from:] (inclusive) to [:to:] (exclusive) | |
| 36 * of the given list [:a:]. | |
| 37 * | |
| 38 * If the given range is invalid an "OutOfRange" error is raised. | |
| 39 * TODO(floitsch): do we want an error? | |
| 40 * | |
| 41 * See [:sort:] for requirements of the [:compare:] function. | |
| 42 */ | |
| 43 static void sortRange(List a, int from, int to, int compare(a, b)) { | |
| 44 if ((from < 0) || (to > a.length) || (to < from)) { | |
| 45 throw "OutOfRange"; | |
| 46 } | |
| 47 _doSort(a, from, to - 1, compare); | |
| 48 } | |
| 49 | |
| 50 /** | |
| 51 * Sorts the list in the interval [:left:] to [:right:] (both inclusive). | |
| 52 */ | |
| 53 static void _doSort(List a, int left, int right, int compare(a, b)) { | |
| 54 if ((right - left) <= _INSERTION_SORT_THRESHOLD) { | |
| 55 insertionSort_(a, left, right, compare); | |
| 56 } else { | |
| 57 _dualPivotQuicksort(a, left, right, compare); | |
| 58 } | |
| 59 } | |
| 60 | |
| 61 static void insertionSort_(List a, int left, int right, int compare(a, b)) { | |
| 62 for (int i = left + 1; i <= right; i++) { | |
| 63 var el = a[i]; | |
| 64 int j = i; | |
| 65 while ((j > left) && (compare(a[j - 1], el) > 0)) { | |
| 66 a[j] = a[j - 1]; | |
| 67 j--; | |
| 68 } | |
| 69 a[j] = el; | |
| 70 } | |
| 71 } | |
| 72 | |
| 73 static void _dualPivotQuicksort(List a, | |
| 74 int left, int right, | |
| 75 int compare(a, b)) { | |
| 76 assert(right - left > _INSERTION_SORT_THRESHOLD); | |
| 77 | |
| 78 // Compute the two pivots by looking at 5 elements. | |
| 79 int sixth = (right - left + 1) ~/ 6; | |
| 80 int index1 = left + sixth; | |
| 81 int index5 = right - sixth; | |
| 82 int index3 = (left + right) ~/ 2; // The midpoint. | |
| 83 int index2 = index3 - sixth; | |
| 84 int index4 = index3 + sixth; | |
| 85 | |
| 86 var el1 = a[index1]; | |
| 87 var el2 = a[index2]; | |
| 88 var el3 = a[index3]; | |
| 89 var el4 = a[index4]; | |
| 90 var el5 = a[index5]; | |
| 91 | |
| 92 // Sort the selected 5 elements using a sorting network. | |
| 93 if (compare(el1, el2) > 0) { var t = el1; el1 = el2; el2 = t; } | |
| 94 if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; } | |
| 95 if (compare(el1, el3) > 0) { var t = el1; el1 = el3; el3 = t; } | |
| 96 if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; } | |
| 97 if (compare(el1, el4) > 0) { var t = el1; el1 = el4; el4 = t; } | |
| 98 if (compare(el3, el4) > 0) { var t = el3; el3 = el4; el4 = t; } | |
| 99 if (compare(el2, el5) > 0) { var t = el2; el2 = el5; el5 = t; } | |
| 100 if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; } | |
| 101 if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; } | |
| 102 | |
| 103 var pivot1 = el2; | |
| 104 var pivot2 = el4; | |
| 105 | |
| 106 // el2 and el4 have been saved in the pivot variables. They will be written | |
| 107 // back, once the partioning is finished. | |
| 108 a[index1] = el1; | |
| 109 a[index3] = el3; | |
| 110 a[index5] = el5; | |
| 111 | |
| 112 a[index2] = a[left]; | |
| 113 a[index4] = a[right]; | |
| 114 | |
| 115 int less = left + 1; // First element in the middle partition. | |
| 116 int great = right - 1; // Last element in the middle partition. | |
| 117 | |
| 118 bool pivots_are_equal = (compare(pivot1, pivot2) == 0); | |
| 119 if (pivots_are_equal) { | |
| 120 var pivot = pivot1; | |
| 121 // Degenerated case where the partioning becomes a dutch national flag | |
| 122 // problem. | |
| 123 // | |
| 124 // [ | < pivot | == pivot | unpartitioned | > pivot | ] | |
| 125 // ^ ^ ^ ^ ^ | |
| 126 // left less k great right | |
| 127 // | |
| 128 // a[left] and a[right] are undefined and are filled after the | |
| 129 // partitioning. | |
| 130 // | |
| 131 // Invariants: | |
| 132 // 1) for x in ]left, less[ : x < pivot. | |
| 133 // 2) for x in [less, k[ : x == pivot. | |
| 134 // 3) for x in ]great, right[ : x > pivot. | |
| 135 for (int k = less; k <= great; k++) { | |
| 136 var ak = a[k]; | |
| 137 int comp = compare(ak, pivot); | |
| 138 if (comp == 0) continue; | |
| 139 if (comp < 0) { | |
| 140 if (k != less) { | |
| 141 a[k] = a[less]; | |
| 142 a[less] = ak; | |
| 143 } | |
| 144 less++; | |
| 145 } else { | |
| 146 // comp > 0. | |
| 147 // | |
| 148 // Find the first element <= pivot in the range [k - 1, great] and | |
| 149 // put [:ak:] there. We know that such an element must exist: | |
| 150 // When k == less, then el3 (which is equal to pivot) lies in the | |
| 151 // interval. Otherwise a[k - 1] == pivot and the search stops at k-1. | |
| 152 // Note that in the latter case invariant 2 will be violated for a | |
| 153 // short amount of time. The invariant will be restored when the | |
| 154 // pivots are put into their final positions. | |
| 155 while (true) { | |
| 156 comp = compare(a[great], pivot); | |
| 157 if (comp > 0) { | |
| 158 great--; | |
| 159 // This is the only location in the while-loop where a new | |
| 160 // iteration is started. | |
| 161 continue; | |
| 162 } else if (comp < 0) { | |
| 163 // Triple exchange. | |
| 164 a[k] = a[less]; | |
| 165 a[less++] = a[great]; | |
| 166 a[great--] = ak; | |
| 167 break; | |
| 168 } else { | |
| 169 // comp == 0; | |
| 170 a[k] = a[great]; | |
| 171 a[great--] = ak; | |
| 172 // Note: if great < k then we will exit the outer loop and fix | |
| 173 // invariant 2 (which we just violated). | |
| 174 break; | |
| 175 } | |
| 176 } | |
| 177 } | |
| 178 } | |
| 179 } else { | |
| 180 // We partition the list into three parts: | |
| 181 // 1. < pivot1 | |
| 182 // 2. >= pivot1 && <= pivot2 | |
| 183 // 3. > pivot2 | |
| 184 // | |
| 185 // During the loop we have: | |
| 186 // [ | < pivot1 | >= pivot1 && <= pivot2 | unpartitioned | > pivot2 | ] | |
| 187 // ^ ^ ^ ^ ^ | |
| 188 // left less k great right | |
| 189 // | |
| 190 // a[left] and a[right] are undefined and are filled after the | |
| 191 // partitioning. | |
| 192 // | |
| 193 // Invariants: | |
| 194 // 1. for x in ]left, less[ : x < pivot1 | |
| 195 // 2. for x in [less, k[ : pivot1 <= x && x <= pivot2 | |
| 196 // 3. for x in ]great, right[ : x > pivot2 | |
| 197 for (int k = less; k <= great; k++) { | |
| 198 var ak = a[k]; | |
| 199 int comp_pivot1 = compare(ak, pivot1); | |
| 200 if (comp_pivot1 < 0) { | |
| 201 if (k != less) { | |
| 202 a[k] = a[less]; | |
| 203 a[less] = ak; | |
| 204 } | |
| 205 less++; | |
| 206 } else { | |
| 207 int comp_pivot2 = compare(ak, pivot2); | |
| 208 if (comp_pivot2 > 0) { | |
| 209 while (true) { | |
| 210 int comp = compare(a[great], pivot2); | |
| 211 if (comp > 0) { | |
| 212 great--; | |
| 213 if (great < k) break; | |
| 214 // This is the only location inside the loop where a new | |
| 215 // iteration is started. | |
| 216 continue; | |
| 217 } else { | |
| 218 // a[great] <= pivot2. | |
| 219 comp = compare(a[great], pivot1); | |
| 220 if (comp < 0) { | |
| 221 // Triple exchange. | |
| 222 a[k] = a[less]; | |
| 223 a[less++] = a[great]; | |
| 224 a[great--] = ak; | |
| 225 } else { | |
| 226 // a[great] >= pivot1. | |
| 227 a[k] = a[great]; | |
| 228 a[great--] = ak; | |
| 229 } | |
| 230 break; | |
| 231 } | |
| 232 } | |
| 233 } | |
| 234 } | |
| 235 } | |
| 236 } | |
| 237 | |
| 238 // Move pivots into their final positions. | |
| 239 // We shrunk the list from both sides (a[left] and a[right] have | |
| 240 // meaningless values in them) and now we move elements from the first | |
| 241 // and third partition into these locations so that we can store the | |
| 242 // pivots. | |
| 243 a[left] = a[less - 1]; | |
| 244 a[less - 1] = pivot1; | |
| 245 a[right] = a[great + 1]; | |
| 246 a[great + 1] = pivot2; | |
| 247 | |
| 248 // The list is now partitioned into three partitions: | |
| 249 // [ < pivot1 | >= pivot1 && <= pivot2 | > pivot2 ] | |
| 250 // ^ ^ ^ ^ | |
| 251 // left less great right | |
| 252 | |
| 253 // Recursive descent. (Don't include the pivot values.) | |
| 254 _doSort(a, left, less - 2, compare); | |
| 255 _doSort(a, great + 2, right, compare); | |
| 256 | |
| 257 if (pivots_are_equal) { | |
| 258 // All elements in the second partition are equal to the pivot. No | |
| 259 // need to sort them. | |
| 260 return; | |
| 261 } | |
| 262 | |
| 263 // In theory it should be enough to call _doSort recursively on the second | |
| 264 // partition. | |
| 265 // The Android source however removes the pivot elements from the recursive | |
| 266 // call if the second partition is too large (more than 2/3 of the list). | |
| 267 if (less < index1 && great > index5) { | |
| 268 while (compare(a[less], pivot1) == 0) { less++; } | |
| 269 while (compare(a[great], pivot2) == 0) { great--; } | |
| 270 | |
| 271 // Copy paste of the previous 3-way partitioning with adaptions. | |
| 272 // | |
| 273 // We partition the list into three parts: | |
| 274 // 1. == pivot1 | |
| 275 // 2. > pivot1 && < pivot2 | |
| 276 // 3. == pivot2 | |
| 277 // | |
| 278 // During the loop we have: | |
| 279 // [ == pivot1 | > pivot1 && < pivot2 | unpartitioned | == pivot2 ] | |
| 280 // ^ ^ ^ | |
| 281 // less k great | |
| 282 // | |
| 283 // Invariants: | |
| 284 // 1. for x in [ *, less[ : x == pivot1 | |
| 285 // 2. for x in [less, k[ : pivot1 < x && x < pivot2 | |
| 286 // 3. for x in ]great, * ] : x == pivot2 | |
| 287 for (int k = less; k <= great; k++) { | |
| 288 var ak = a[k]; | |
| 289 int comp_pivot1 = compare(ak, pivot1); | |
| 290 if (comp_pivot1 == 0) { | |
| 291 if (k != less) { | |
| 292 a[k] = a[less]; | |
| 293 a[less] = ak; | |
| 294 } | |
| 295 less++; | |
| 296 } else { | |
| 297 int comp_pivot2 = compare(ak, pivot2); | |
| 298 if (comp_pivot2 == 0) { | |
| 299 while (true) { | |
| 300 int comp = compare(a[great], pivot2); | |
| 301 if (comp == 0) { | |
| 302 great--; | |
| 303 if (great < k) break; | |
| 304 // This is the only location inside the loop where a new | |
| 305 // iteration is started. | |
| 306 continue; | |
| 307 } else { | |
| 308 // a[great] < pivot2. | |
| 309 comp = compare(a[great], pivot1); | |
| 310 if (comp < 0) { | |
| 311 // Triple exchange. | |
| 312 a[k] = a[less]; | |
| 313 a[less++] = a[great]; | |
| 314 a[great--] = ak; | |
| 315 } else { | |
| 316 // a[great] == pivot1. | |
| 317 a[k] = a[great]; | |
| 318 a[great--] = ak; | |
| 319 } | |
| 320 break; | |
| 321 } | |
| 322 } | |
| 323 } | |
| 324 } | |
| 325 } | |
| 326 // The second partition has now been cleared of pivot elements and looks | |
| 327 // as follows: | |
| 328 // [ * | > pivot1 && < pivot2 | * ] | |
| 329 // ^ ^ | |
| 330 // less great | |
| 331 // Sort the second partition using recursive descent. | |
| 332 _doSort(a, less, great, compare); | |
| 333 } else { | |
| 334 // The second partition looks as follows: | |
| 335 // [ * | >= pivot1 && <= pivot2 | * ] | |
| 336 // ^ ^ | |
| 337 // less great | |
| 338 // Simply sort it by recursive descent. | |
| 339 _doSort(a, less, great, compare); | |
| 340 } | |
| 341 } | |
| 342 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 11239004:
Move DualPivotQuicksort from coreimpl to core as _Sort. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart