LGTM On Thu, Sep 25, 2008 at 3:11 PM, <[EMAIL PROTECTED]> wrote: > Reviewers: Mads Ager, > > Description: > Tuning quick sort. > > Tuning the quick sort algorithm to avoid degenerating to an n^2 > algorithm when all elements are the same. > > Please review this at http://codereview.chromium.org/4083 > > Affected files: > M src/array.js > > > Index: src/array.js > =================================================================== > --- src/array.js (revision 374) > +++ src/array.js (working copy) > @@ -647,7 +647,7 @@ > > > function ArraySort(comparefn) { > - // Standard in-place HeapSort algorithm. > + // In-place QuickSort algorithm. > > function Compare(x,y) { > if (IS_UNDEFINED(x)) { > @@ -672,21 +672,26 @@ > if (from >= to - 1) return; > var pivot_index = $floor($random() * (to - from)) + from; > var pivot = a[pivot_index]; > - a[pivot_index] = a[to - 1]; > - a[to - 1] = pivot; > - var partition = from; > - for (var i = from; i < to - 1; i++) { > + var low_end = from; // Upper bound of the elements lower than pivot. > + var high_start = to; // Lower bound of the elements greater than pivot. > + for (var i = from; i < high_start; ) { > var element = a[i]; > - if (Compare(element, pivot) < 0) { > - a[i] = a[partition]; > - a[partition] = element; > - partition++; > + var order = Compare(element, pivot); > + if (order < 0) { > + a[i] = a[low_end]; > + a[low_end] = element; > + low_end++; > + i++; > + } else if (order > 0) { > + high_start--; > + a[i] = a[high_start]; > + a[high_start] = element; > + } else { // order == 0 > + i++; > } > } > - a[to - 1] = a[partition]; > - a[partition] = pivot; > - QuickSort(a, from, partition); > - QuickSort(a, partition + 1, to); > + QuickSort(a, from, low_end); > + QuickSort(a, high_start, to); > } > > var old_length = ToUint32(this.length); > > >
--~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
