-
Notifications
You must be signed in to change notification settings - Fork 3
/
comb-sort.js
39 lines (35 loc) · 1.04 KB
/
comb-sort.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
* CODE: https://www.w3resource.com/javascript-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-9.php
*
* Comb sort is a relatively simple sorting algorithm originally designed by
Włodzimierz Dobosiewicz in 1980. Later it was rediscovered by Stephen Lacey
and Richard Box in 1991. Comb sort improves on bubble sort.
*
* MORE INFO: https://en.wikipedia.org/wiki/Comb_sort
*/
function isSorted(arr) {
return arr.every((num, index) => index === 0 || arr[index - 1] <= num);
}
export function combSort(arr) {
let iteration_count = 0;
let gap = arr.length - 2;
let decrease_factor = 1.25;
while (!isSorted(arr)) {
if (iteration_count > 0) {
gap = gap === 1 ? gap : Math.floor(gap / decrease_factor);
}
let front = 0;
let back = gap;
while (back <= arr.length - 1) {
if (arr[front] > arr[back]) {
let temp = arr[front];
arr[front] = arr[back];
arr[back] = temp;
}
front += 1;
back += 1;
}
iteration_count += 1;
}
return arr;
}