Comb Sort

Wednesday, June 2, 2010 by gradbot

Comb sort tries to overcome bubble sorts problems by comparing values far away from one another at first and then slowly reducing the gap until it's comparing adjacent values.
Wikipedia on Comb sort.








algorithms.sort.comb = function(array, predicate){
var found = true;
var length = array.length;
var shrink_factor = 1.247330950103979;
var gap = length;
while (found || gap > 1) {
found = false;

gap = gap / shrink_factor;
if (gap < 1) {
gap = 1;
}

var i_gap = Math.ceil(gap);
for (var i = 0; i < length - i_gap; i++) {
if (!predicate(array, i, i + i_gap)) {
array.swap(i, i + i_gap);
found = true;
}
}
}
};


Filed under , , , having