Skip to content

Commit 1806dae

Browse files
TornjVTornjV
committed
Merge pull request algorithm-visualizer#43 from Arthurlpgc/gh-pages
Adding a Radix LSD
2 parents e001535 + 90e1c71 commit 1806dae

5 files changed

Lines changed: 71 additions & 4 deletions

File tree

‎algorithm/category.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,8 @@
3030
"bubble": "Bubble Sort",
3131
"quick": "Quicksort",
3232
"merge": "Mergesort",
33-
"heap" : "Heap Sort"
33+
"heap" : "Heap Sort",
34+
"radixlsd" : "Radix LSD sort"
3435
}
3536
},
3637
"string": {

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

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
tracer._print('original array = [' + D[0].join(', ') + ']');
2+
tracer._sleep(1000);
3+
tracer._pace(300);
4+
function pow(base, expo){
5+
var ans = 1;
6+
for(var i = 0; i < expo;i++){
7+
ans *= base;
8+
}
9+
return ans;
10+
}
11+
for(var exp = 0; exp < 6;exp ++){
12+
tracer._print("Bit "+exp);
13+
for(var i = 0; i < D[0].length; i++){
14+
tracer._select(0, i);
15+
D[2][ parseInt( D[0][i] / pow(10, exp) % 10) ] += 1;
16+
tracer._notify(2, parseInt( D[0][i] / pow(10, exp) % 10) );
17+
tracer._deselect(0, i);
18+
}
19+
for(var i = 1; i < 10; i++){
20+
tracer._select(2, i - 1);
21+
D[2][i] += D[2][i - 1];
22+
tracer._notify(2, i);
23+
tracer._deselect(2, i - 1);
24+
}
25+
for(var i = D[0].length - 1; i >= 0; i--){
26+
tracer._select(0, i);
27+
D[2][parseInt( D[0][i] / pow(10, exp) % 10) ] -= 1;
28+
tracer._notify(2, parseInt( D[0][i] / pow(10, exp) % 10) );
29+
D[1][ D[2][ parseInt( D[0][i] / pow(10, exp) % 10) ] ] = D[0][i];
30+
tracer._notify(1, D[2][ parseInt( D[0][i] / pow(10, exp) % 10) ] );
31+
tracer._deselect(0, i);
32+
}
33+
for(var i = 0; i < D[0].length; i++){
34+
tracer._select(1, i);
35+
D[0][i] = D[1][i];
36+
tracer._notify(0, i);
37+
tracer._deselect(1, i);
38+
}
39+
for(var i = 0; i < 10; i++){
40+
D[2][i] = 0;
41+
tracer._notify(2, i);
42+
}
43+
}
44+
tracer._print('sorted array = [' + D[0].join(', ') + ']');

‎algorithm/sorting/radixlsd/basic/data.js‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
var tracer = new Array2DTracer();
2+
var k = [5,4,3,5,7,5,6,9];
3+
var D = [
4+
k,
5+
Array1D.random(k.length),
6+
[0,0,0,0,0,0,0,0,0,0]
7+
];
8+
tracer._setData(D);

‎algorithm/sorting/radixlsd/desc.json‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Radix LSD Sort": "Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.",
3+
"Complexity": {
4+
"time": "worst O(n), best O(n), average O(n)",
5+
"space": "always O(n)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Radix_sort'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Basic"
12+
}
13+
}

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

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,11 +5,12 @@ for (var i = 0; i < D.length - 1; i++) {
55
var minJ = i;
66
tracer._select(i);
77
for (var j = i + 1; j < D.length; j++) {
8+
tracer._select(j);
89
if (D[j] < D[minJ]) {
9-
tracer._select(j);
10+
tracer._notify(j);
1011
minJ = j;
11-
tracer._deselect(j);
1212
}
13+
tracer._deselect(j);
1314
}
1415
if (minJ != i) {
1516
tracer._print('swap ' + D[i] + ' and ' + D[minJ]);
@@ -20,4 +21,4 @@ for (var i = 0; i < D.length - 1; i++) {
2021
}
2122
tracer._deselect(i);
2223
}
23-
tracer._print('sorted array = [' + D.join(', ') + ']');
24+
tracer._print('sorted array = [' + D.join(', ') + ']');

0 commit comments

Comments
 (0)