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 139 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
150 | 150 |
151 a[index2] = a[left]; | 151 a[index2] = a[left]; |
152 a[index4] = a[right]; | 152 a[index4] = a[right]; |
153 | 153 |
154 int less = left + 1; // First element in the middle partition. | 154 int less = left + 1; // First element in the middle partition. |
155 int great = right - 1; // Last element in the middle partition. | 155 int great = right - 1; // Last element in the middle partition. |
156 | 156 |
157 bool pivots_are_equal = (compare(pivot1, pivot2) == 0); | 157 bool pivots_are_equal = (compare(pivot1, pivot2) == 0); |
158 if (pivots_are_equal) { | 158 if (pivots_are_equal) { |
159 var pivot = pivot1; | 159 var pivot = pivot1; |
160 // Degenerated case where the partitioning becomes a dutch national flag | 160 // Degenerated case where the partitioning becomes a Dutch national flag |
161 // problem. | 161 // problem. |
162 // | 162 // |
163 // [ | < pivot | == pivot | unpartitioned | > pivot | ] | 163 // [ | < pivot | == pivot | unpartitioned | > pivot | ] |
164 // ^ ^ ^ ^ ^ | 164 // ^ ^ ^ ^ ^ |
165 // left less k great right | 165 // left less k great right |
166 // | 166 // |
167 // a[left] and a[right] are undefined and are filled after the | 167 // a[left] and a[right] are undefined and are filled after the |
168 // partitioning. | 168 // partitioning. |
169 // | 169 // |
170 // Invariants: | 170 // Invariants: |
(...skipping 205 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
376 } else { | 376 } else { |
377 // The second partition looks as follows: | 377 // The second partition looks as follows: |
378 // [ * | >= pivot1 && <= pivot2 | * ] | 378 // [ * | >= pivot1 && <= pivot2 | * ] |
379 // ^ ^ | 379 // ^ ^ |
380 // less great | 380 // less great |
381 // Simply sort it by recursive descent. | 381 // Simply sort it by recursive descent. |
382 _doSort(a, less, great, compare); | 382 _doSort(a, less, great, compare); |
383 } | 383 } |
384 } | 384 } |
385 } | 385 } |
OLD | NEW |