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 |