--description--

Implement a comb sort.

The Comb Sort is a variant of the Bubble Sort.

Like the Shell sort, the Comb Sort increases the gap used in comparisons and exchanges.

Dividing the gap by $(1-e^{-\varphi})^{-1} \approx 1.247330950103979$ works best, but 1.3 may be more practical.

Some implementations use the insertion sort once the gap is less than a certain amount.

Variants:

<ul> <li>Combsort11 makes sure the gap ends in (11, 8, 6, 4, 3, 2, 1), which is significantly faster than the other two possible endings.</li> <li>Combsort with different endings changes to a more efficient sort when the data is almost sorted (when the gap is small). Comb sort with a low gap isn't much better than the Bubble Sort.</li> </ul>

Pseudocode:

<pre>function combsort(array input) gap := input.size //initialize gap size loop until gap = 1 and swaps = 0 //update the gap value for a next comb. Below is an example gap := int(gap / 1.25) if gap < 1 //minimum gap is 1 gap := 1 end if i := 0 swaps := 0 //see <a href='https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort' target='_blank'>Bubble Sort</a> for an explanation //a single "comb" over the input list loop until i + gap >= input.size //see <a href='https://rosettacode.org/wiki/Sorting_algorithms/Shell_sort' target='_blank'>Shell sort</a> for similar idea if input[i] > input[i+gap] swap(input[i], input[i+gap]) swaps := 1 // Flag a swap has occurred, so the // list is not guaranteed sorted end if i := i + 1 end loop end loop end function </pre>

--instructions--

Write a function that sorts a given array using Comb sort.

--hints--

combSort should be a function.

assert(typeof combSort == 'function');

combSort([25, 32, 12, 7, 20]) should return an array.

assert(Array.isArray(combSort([25, 32, 12, 7, 20])));

combSort([25, 32, 12, 7, 20]) should return [7, 12, 20, 25, 32].

assert.deepEqual(combSort([25, 32, 12, 7, 20]), [7, 12, 20, 25, 32]);

combSort([38, 45, 35, 8, 13]) should return [8, 13, 35, 38, 45].

assert.deepEqual(combSort([38, 45, 35, 8, 13]), [8, 13, 35, 38, 45]);

combSort([43, 36, 20, 34, 24]) should return [20, 24, 34, 36, 43].

assert.deepEqual(combSort([43, 36, 20, 34, 24]), [20, 24, 34, 36, 43]);

combSort([12, 33, 26, 18, 1, 16, 38]) should return [1, 12, 16, 18, 26, 33, 38].

assert.deepEqual(combSort([12, 33, 26, 18, 1, 16, 38]), [
  1,
  12,
  16,
  18,
  26,
  33,
  38
]);

combSort([3, 39, 48, 16, 1, 4, 29]) should return [1, 3, 4, 16, 29, 39, 48].

assert.deepEqual(combSort([3, 39, 48, 16, 1, 4, 29]), [
  1,
  3,
  4,
  16,
  29,
  39,
  48
]);

--seed--

--seed-contents--

function combSort(arr) {

}

--solutions--

function combSort(arr) {
  function is_array_sorted(arr) {
    var sorted = true;
    for (var i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        sorted = false;
        break;
      }
    }
    return sorted;
  }
  var iteration_count = 0;
  var gap = arr.length - 2;
  var decrease_factor = 1.25;

  // Until array is not sorted, repeat iterations
  while (!is_array_sorted(arr)) {
    // If not first gap
    if (iteration_count > 0)
      // Calculate gap
      gap = gap == 1 ? gap : Math.floor(gap / decrease_factor);

    // Set front and back elements and increment to a gap
    var front = 0;
    var back = gap;
    while (back <= arr.length - 1) {
      // If elements are not ordered swap them
      if (arr[front] > arr[back]) {
        var temp = arr[front];
        arr[front] = arr[back];
        arr[back] = temp;
      }

      // Increment and re-run swapping
      front += 1;
      back += 1;
    }
    iteration_count += 1;
  }

  return arr;
}