Skip to content

Commit 1768b26

Browse files
TornjVTornjV
committed
Merge pull request algorithm-visualizer#59 from makintunde/master
Add Shell Sort
2 parents 44bcee2 + 41597bf commit 1768b26

3 files changed

Lines changed: 47 additions & 0 deletions

File tree

‎algorithm/sorting/shell/basic/code.js‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
logger._print('Original array = [' + D.join(', ') + ']');
2+
var N = D.length;
3+
4+
for (var gap = N; gap = parseInt(gap / 2);) {
5+
logger._print('');
6+
logger._print('Gap of ' + gap);
7+
for (var i = gap; i < N; i++) {
8+
tracer._select(i)._select(i - gap)._wait();
9+
var k = D[i];
10+
logger._print('Holding: ' + k)
11+
for (var j = i; j >= gap && k < D[j - gap]; j -= gap) {
12+
logger._print(k + ' < ' + D[j - gap]);
13+
D[j] = D[j - gap];
14+
tracer._notify(j, D[j])._wait();
15+
tracer._denotify(j);
16+
}
17+
var old = D[j];
18+
D[j] = k;
19+
if (old != k) {
20+
tracer._notify(j,D[j])._wait();
21+
tracer._denotify(j);
22+
logger._print('Swapped ' + D[j] + ' with ' + old);
23+
}
24+
25+
tracer._deselect(i)._deselect(i - gap);
26+
}
27+
}
28+
tracer._clear();
29+
logger._print('')
30+
logger._print('Sorted array = [' + D.join(', ') + ']');

‎algorithm/sorting/shell/basic/desc.js‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
var tracer = new Array1DTracer();
2+
var logger = new LogTracer();
3+
var D = Array1D.random(15);
4+
tracer._setData(D);

‎algorithm/sorting/shell/desc.json‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Shellsort": "Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.",
3+
"Complexity": {
4+
"time": "best O(n log n), average - depends on 'gap sequence'",
5+
"space": "worst O(n) total, O(1) auxilliary"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Shellsort'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Basic"
12+
}
13+
}

0 commit comments

Comments
 (0)