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