CombSort.js

/**
 * Comb sort improves on bubble sort.
 *
 * The basic idea is to eliminate turtles, or small values
 * near the end of the list, since in a bubble sort these slow the sorting
 * down tremendously. Rabbits, large values around the beginning of the list,
 * do not pose a problem in bubble sort.
 *
 * In bubble sort, when any two elements are compared, they always have a
 * gap (distance from each other) of 1. The basic idea of comb sort is
 * that the gap can be much more than 1. The inner loop of bubble sort,
 * which does the actual swap, is modified such that gap between swapped
 * elements goes down (for each iteration of outer loop) in steps of
 * a "shrink factor" k: [ n/k, n/k2, n/k3, ..., 1 ].
 *
 * Wikipedia: https://en.wikipedia.org/wiki/Comb_sort
 */

/**
 * combSort returns an array of numbers sorted in increasing order.
 *
 * @param {number[]} list The array of numbers to sort.
 * @return {number[]} The array of numbers sorted in increasing order.
 */
function combSort (list) {
  if (list.length === 0) {
    return list
  }
  const shrink = 1.3
  let gap = list.length
  let isSwapped = true
  let i = 0

  while (gap > 1 || isSwapped) {
    // Update the gap value for a next comb
    gap = parseInt(parseFloat(gap) / shrink, 10)

    isSwapped = false
    i = 0

    while (gap + i < list.length) {
      if (list[i] > list[i + gap]) {
        [list[i], list[i + gap]] = [list[i + gap], list[i]]
        isSwapped = true
      }
      i += 1
    }
  }
  return list
}

export { combSort }