Skip to content

Commit 4f0620d

Browse files
64json64json
authored
Merge pull request algorithm-visualizer#173 from jarettgross/counting-sort
Implemented counting sort
2 parents bacbf0f + cdb6d65 commit 4f0620d

File tree

8 files changed

+69
-7
lines changed

8 files changed

+69
-7
lines changed

‎algorithm/category.json

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,7 @@
7070
"list": {
7171
"bubble": "Bubble Sort",
7272
"comb": "Comb Sort",
73+
"counting": "Counting Sort",
7374
"cycle": "Cycle Sort",
7475
"heap": "Heapsort",
7576
"insertion": "Insertion Sort",

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

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
//set counts values
2+
for (let i = 0; i < A.length; i++) {
3+
tracer._select(0, i)._wait();
4+
counts[A[i]]++;
5+
tracer._notify(1, A[i], D[1][A[i]])._wait();
6+
tracer._deselect(0, i);
7+
tracer._denotify(1, A[i], D[1][A[i]])._wait();
8+
}
9+
10+
//sort
11+
var i = 0;
12+
for (var j = 0; j <= maxValue; j++) {
13+
while (counts[j] > 0) {
14+
tracer._select(1, j)._wait();
15+
sortedA[i] = j;
16+
counts[j]--;
17+
tracer._notify(1, j, D[1][j]);
18+
tracer._notify(2, i, D[2][i])._wait();
19+
tracer._deselect(1, j);
20+
tracer._denotify(1, j, D[1][j]);
21+
tracer._denotify(2, i, D[2][i])._wait();
22+
i++;
23+
}
24+
}

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

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
var maxValue = 9;
2+
var arrSize = 10;
3+
4+
//initialize array values
5+
var A = Array1D.random(arrSize, 0, maxValue);
6+
var counts = [];
7+
var sortedA = [];
8+
for (let i = 0; i <= maxValue; i++) {
9+
counts[i] = 0;
10+
if (i < arrSize) sortedA[i] = 0;
11+
}
12+
var D = [
13+
A,
14+
counts,
15+
sortedA
16+
];
17+
18+
var tracer = new Array2DTracer();
19+
tracer._setData(D);

‎algorithm/sorting/counting/desc.json

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Counting Sort": "Counting sort is a sorting algorithm for a collection of objects. Sorting is done according to the keys (small integers) of the objects. This works by counting the number of objects that have each distinct key value, and then using those counts to determine the positions of each key value.",
3+
"Complexity": {
4+
"time": "worst O(n+k), best O(n), average O(n+k) where n is the number of elements in the input array and k is the range of the output",
5+
"space": "worst O(n+k)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Counting_sort'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Counting sort"
12+
}
13+
}

‎public/algorithm_visualizer.js

Lines changed: 9 additions & 4 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎public/algorithm_visualizer.js.map

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎public/algorithm_visualizer.min.js

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎public/algorithm_visualizer.min.js.map

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

0 commit comments

Comments
 (0)