Quick Sort

Friday, June 4, 2010 by gradbot

Quick sort is a classic divide and conquer algorithm. It works by picking a pivot element and dividing the list into two sub list based on if the elements are less than or grater than the pivot element. This is repeated with new pivots in the smaller lists until the list size equals one.

Implementing this algorithm in place is interesting since you don't know how many elements are going to go on each side of the pivot. To get around this you can swap the pivot element with the last element in the list. Then you iterate over the list moving all the elements less than the pivot before all the elements greater than the pivot. Once this is done you swap the last element again, which is the pivot, with the first element after all the elements less than the pivot. This puts the pivot in the middle and the first element that is greater than the pivot in the last position. The pivot is now in the correct position with all the elements less than it to the left and all the elements greater than it to the right. Wikipedia on Quick sort.



algorithms.sort.quick = function(array, predicate) {
    var quick = function(left, right) {
        if (right >= left) {
            var pivot = Math.floor((right + left) / 2);
            var store = left;
            array.swap(right, pivot);
            // right is now the pivot
            for (var i = left; i <= right; i++) {
                if (predicate(array, i, right)) {
                    array.swap(i, store);
                    store++;
                } 
            }
            array.swap(right, store);
            // right is no longer the pivot
            quick(left, store - 1);
            quick(store + 1, right);
        }
    };
    quick(0, array.length - 1);
};

Filed under , , , having  

0 comments: