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