JavaScript/Sorts/CombSort.js at master · TheAlgorithms/JavaScript · GitHub

History

52 lines (47 loc) · 1.49 KB

Raw

/**

* 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 }

JavaScript/Sorts/CombSort.js at master · TheAlgorithms/JavaScript · GitHub

Uh oh!

Uh oh!

JavaScript/Sorts/CombSort.js at master · TheAlgorithms/JavaScript · GitHub

Uh oh!

Uh oh!

Expand file tree

Breadcrumbs

CombSort.js

Latest commit

History

Breadcrumbs

CombSort.js

File metadata and controls