Chiamaka · August 26, 2018 14:35 · Aug 26, 2018
diff --git a/countingSort.js b/countingSort.js
@@ -0,0 +1,42 @@
+/*
+  Some background:
+  - Most sorting algorithms like mergesort, quick sort, selection sort, run in O(n log n) time
+  - Counting sort says it can do better with O(n) time but with a caveat of using more space (O(n) space)
+  - Counting sort requires 2 ingredients: 
+    1. The unsorted array
+    2. The higest possible value in the array. So like the range
+*/
+const unsortedScores = [2, 5, 10, 1, 3, 7, 9];
+const HIGHEST_POSSIBLE_SCORE = 10;
+
+// O(n) time and space
+function countingSort(unsortedScores, max) {
+  // First we create an empty array that we are gonna populate with zeros
+  // So we are going to have a 10 size array all filled with 0's
+  // So countArray = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
+  // The index of each item in the array corresponds to the numbers in the unsortedScores array
+  const countArray = [];
+  for (let i=0; i<=max; i++) {
+    countArray[i] = 0; 
+  }
+
+  // Loop through the unsortedScores array and whenever you see the number, add 1
+  // countArray = [0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1]
+  unsortedScores.forEach(function (i) {
+     countArray[i]++;
+  });
+
+  // Wherever we see a value that is more than 0, we push the index of that into a new sortedArray
+
+  const sortedArray = [];
+  let currentIndex = 0;
+  for (let num=0; num < max; num++) {
+    const count = countArray[num];
+    if (count > 0) {
+      for (let times=0; times < count; times++) {
+        sortedArray[currentIndex] = num;
+      }
+    }
+  } 
+  return sortedArray;
+}
No results found