| OLD | NEW |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 part of dart._internal; | 5 part of dart._internal; |
| 6 | 6 |
| 7 /** | 7 /** |
| 8 * Dual-Pivot Quicksort algorithm. | 8 * Dual-Pivot Quicksort algorithm. |
| 9 * | 9 * |
| 10 * This class implements the dual-pivot quicksort algorithm as presented in | 10 * This class implements the dual-pivot quicksort algorithm as presented in |
| (...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 100 if (compare(el1, el4) > 0) { var t = el1; el1 = el4; el4 = t; } | 100 if (compare(el1, el4) > 0) { var t = el1; el1 = el4; el4 = t; } |
| 101 if (compare(el3, el4) > 0) { var t = el3; el3 = el4; el4 = t; } | 101 if (compare(el3, el4) > 0) { var t = el3; el3 = el4; el4 = t; } |
| 102 if (compare(el2, el5) > 0) { var t = el2; el2 = el5; el5 = t; } | 102 if (compare(el2, el5) > 0) { var t = el2; el2 = el5; el5 = t; } |
| 103 if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; } | 103 if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; } |
| 104 if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; } | 104 if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; } |
| 105 | 105 |
| 106 var pivot1 = el2; | 106 var pivot1 = el2; |
| 107 var pivot2 = el4; | 107 var pivot2 = el4; |
| 108 | 108 |
| 109 // el2 and el4 have been saved in the pivot variables. They will be written | 109 // el2 and el4 have been saved in the pivot variables. They will be written |
| 110 // back, once the partioning is finished. | 110 // back, once the partitioning is finished. |
| 111 a[index1] = el1; | 111 a[index1] = el1; |
| 112 a[index3] = el3; | 112 a[index3] = el3; |
| 113 a[index5] = el5; | 113 a[index5] = el5; |
| 114 | 114 |
| 115 a[index2] = a[left]; | 115 a[index2] = a[left]; |
| 116 a[index4] = a[right]; | 116 a[index4] = a[right]; |
| 117 | 117 |
| 118 int less = left + 1; // First element in the middle partition. | 118 int less = left + 1; // First element in the middle partition. |
| 119 int great = right - 1; // Last element in the middle partition. | 119 int great = right - 1; // Last element in the middle partition. |
| 120 | 120 |
| 121 bool pivots_are_equal = (compare(pivot1, pivot2) == 0); | 121 bool pivots_are_equal = (compare(pivot1, pivot2) == 0); |
| 122 if (pivots_are_equal) { | 122 if (pivots_are_equal) { |
| 123 var pivot = pivot1; | 123 var pivot = pivot1; |
| 124 // Degenerated case where the partioning becomes a dutch national flag | 124 // Degenerated case where the partitioning becomes a dutch national flag |
| 125 // problem. | 125 // problem. |
| 126 // | 126 // |
| 127 // [ | < pivot | == pivot | unpartitioned | > pivot | ] | 127 // [ | < pivot | == pivot | unpartitioned | > pivot | ] |
| 128 // ^ ^ ^ ^ ^ | 128 // ^ ^ ^ ^ ^ |
| 129 // left less k great right | 129 // left less k great right |
| 130 // | 130 // |
| 131 // a[left] and a[right] are undefined and are filled after the | 131 // a[left] and a[right] are undefined and are filled after the |
| 132 // partitioning. | 132 // partitioning. |
| 133 // | 133 // |
| 134 // Invariants: | 134 // Invariants: |
| (...skipping 201 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 336 } else { | 336 } else { |
| 337 // The second partition looks as follows: | 337 // The second partition looks as follows: |
| 338 // [ * | >= pivot1 && <= pivot2 | * ] | 338 // [ * | >= pivot1 && <= pivot2 | * ] |
| 339 // ^ ^ | 339 // ^ ^ |
| 340 // less great | 340 // less great |
| 341 // Simply sort it by recursive descent. | 341 // Simply sort it by recursive descent. |
| 342 _doSort(a, less, great, compare); | 342 _doSort(a, less, great, compare); |
| 343 } | 343 } |
| 344 } | 344 } |
| 345 } | 345 } |
| OLD | NEW |