Improve visualization of Counting Sort

64json · 64json · commit 83cb2911dfab · 2019-02-05T20:41:10.000-05:00
diff --git a/Divide and Conquer/Counting Sort/code.js b/Divide and Conquer/Counting Sort/code.js
@@ -1,46 +1,74 @@
-const { Array2DTracer, Randomize } = require('algorithm-visualizer');
+// import visualization libraries {
+const { Array1DTracer, Randomize } = require('algorithm-visualizer');
+// }
 
-const maxValue = 9;
-const arrSize = 10;
+// define tracer variables {
+const arrayTracer = new Array1DTracer('Array');
+const countsTracer = new Array1DTracer('Counts');
+const sortedArrayTracer = new Array1DTracer('Sorted Array');
+// }
 
-// initialize array values
-const A = new Randomize.Array1D(arrSize, new Randomize.Integer(0, maxValue)).create();
-const counts = [];
-const sortedA = [];
-for (let i = 0; i <= maxValue; i++) {
-  counts[i] = 0;
-  if (i < arrSize) sortedA[i] = 0;
-}
-const D = [
-  A,
-  counts,
-  sortedA,
-];
+// define input variables
+const N = 20; // the size of an array
+const array = new Randomize.Array1D(N, new Randomize.Integer(0, 9)).create();
 
-const tracer = new Array2DTracer();
-tracer.set(D).delay();
+(function main() {
+  // find the maximum value that will decide the size of counts array
+  const max = Math.max(...array);
+  const counts = new Array(max + 1).fill(0);
+  // visualize {
+  arrayTracer.set(array);
+  countsTracer
+    .set(counts)
+    .delay();
+  // }
 
-// set counts values
-for (let i = 0; i < A.length; i++) {
-  tracer.select(0, i).delay();
-  counts[A[i]]++;
-  tracer.patch(1, A[i], D[1][A[i]]).delay();
-  tracer.deselect(0, i);
-  tracer.depatch(1, A[i], D[1][A[i]]).delay();
-}
+  // store counts of each number
+  for (let i = 0; i < N; i++) {
+    const number = array[i];
+    counts[number]++;
+    // visualize {
+    arrayTracer.select(i);
+    countsTracer
+      .patch(number, counts[number])
+      .delay()
+      .depatch(number);
+    arrayTracer.deselect(i);
+    // }
+  }
+
+  // calculate the prefix sums
+  for (let i = 1; i <= max; i++) {
+    counts[i] += counts[i - 1];
+    // visualize {
+    countsTracer
+      .select(i - 1)
+      .patch(i, counts[i])
+      .delay()
+      .depatch(i)
+      .deselect(i - 1);
+    // }
+  }
 
-// sort
-let i = 0;
-for (let j = 0; j <= maxValue; j++) {
-  while (counts[j] > 0) {
-    tracer.select(1, j).delay();
-    sortedA[i] = j;
-    counts[j]--;
-    tracer.patch(1, j, D[1][j]);
-    tracer.patch(2, i, D[2][i]).delay();
-    tracer.deselect(1, j);
-    tracer.depatch(1, j, D[1][j]);
-    tracer.depatch(2, i, D[2][i]).delay();
-    i++;
+  // create a sorted array based on the prefix sums
+  const sortedArray = new Array(N);
+  // visualize {
+  sortedArrayTracer.set(sortedArray);
+  // }
+  for (let i = N - 1; i >= 0; i--) {
+    const number = array[i];
+    const count = counts[number];
+    sortedArray[count - 1] = number;
+    // visualize {
+    arrayTracer.select(i);
+    countsTracer.select(number);
+    sortedArrayTracer
+      .patch(count - 1, sortedArray[count - 1])
+      .delay()
+      .depatch(count - 1);
+    countsTracer.deselect(number);
+    arrayTracer.deselect(i);
+    // }
+    counts[number]--;
   }
-}
+})();
