| 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 |