forked from mgechev/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathshellsort.js
More file actions
49 lines (39 loc) · 1.1 KB
/
shellsort.js
File metadata and controls
49 lines (39 loc) · 1.1 KB
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
40
41
42
43
44
45
46
47
48
49
(function (exports) {
'use strict';
function compare(a, b) {
return a - b;
}
/**
* Shellsort
*
* Shellsort uses the gaps 701, 301, 132, 57, 23, 10, 4, 1 and uses
* insertion sort to sort the sub-arrays which match for the different gaps.
*/
var shellSort = (function () {
var gaps = [701, 301, 132, 57, 23, 10, 4, 1];
/**
* Shellsort which uses the gaps in the lexical scope of the IIFE.
*
* @public
* @param {array} array Array which should be sorted
* @return {array} Sorted array
*/
return function (array, cmp) {
cmp = cmp || compare;
var gap, current;
for (var k = 0; k < gaps.length; k += 1) {
gap = gaps[k];
for (var i = gap; i < array.length; i += gap) {
current = array[i];
for (var j = i;
j >= gap && cmp(array[j - gap], current) > 0; j -= gap) {
array[j] = array[j - gap];
}
array[j] = current;
}
}
return array;
};
}());
exports.shellSort = shellSort;
}(typeof exports === 'undefined' ? window : exports));