Gnome Sort

Thursday, June 3, 2010 by gradbot

Gnome sort works by stepping forward in the list if two elements are in order. If they are out of order it swaps them and steps back. This behavior emulates insertion sort but with many swaps. Wikipedia on Gnome sort.



algorithms.sort.gnome = function(array, predicate){
    var i = 0;
    var length = array.length;
    while (i < length - 1) {
        if (!predicate(array, i, i + 1)) {
            array.swap(i, i + 1);
            if (i > 0) {
                i--;
            }
        } else {
            i++;
        }
    }
};

Filed under , , , having