combsort.js

/* comb sort works like a bubble sort, but adds a gap to each pass 
 * to help neutralize the inefficiencies of small values at the end 
 * of the unsorted list, called "turtles".  the iteration ends when 
 * no elements were swapped during the last comb through the list.
 * efficiency: O(n^2)
 */

function combSort(arr) {
  
  // save array length in a variable
  var length = arr.length;
  
  // save gap in a variable initialized to length
  var gap = length;
  
  // initialize the shrink factor--1.3 is optimal
  var shrink = 1.3;
  
  do {
    
    // reduce the gap by the shrink factor
    gap = Math.floor(gap / shrink);
    
    // assume done unless a swap occurs during this comb
    var done = true;
    
    // go through the array, swapping 
    // elements separated by the gap if necessary
    for (var i = 0, j = gap; j < length; i++, j++) {
      if (arr[i] > arr[j]) {
        
        // we need to go through the array at least once more
        done = false;
        
        // swap the out of order elements
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  } while (!done)

  return arr;
}


var arr = [3391,2,6,-234,43,0,21,2,53,8,-39];

console.log("original : " + arr);
console.log("sorted : " + combSort(arr));