Simple Counting Sort

Sorting data takes time.

So, why does counting sort have a different time complexity than the merge, bubble, heap and other sorts, why is there a variable k in the time complexity?

countingSort([9,1,0,4,6,5,7,8,1,3,2,3,3])

function countingSort(arrayToSort) {

   // 1.
   let i; 
   let indexOfReturn = 0;
   let count = [];

   // 2.
   for (i = 0; i <= 9; i++) {
      count[i] = 0;
   }

   // 3.
   for (i = 0; i < arrayToSort.length; i++) {
      count[arr[i]]++;
   }

   // 4.
   for (i = 0; i <= 9; i++) {
      while (count[i]-- > 0) {
         arrayToSort[indexOfReturn++] = i;
      }
   }
   return arrayToSort;
}


//output => [0,1,1,2,3,3,3,4,5,6,7,8,9]

This is complicated so let's break it down into 4 components:

1. Variables needed

//We are using a base 10 counting sort so the minimum 
//digit is 0 and the maximum digit is 9

//declaring i for index as a let to use in our for loops
let i; 

//declaring the starting index of the returnArray,
//which will just be a modification of the ArrayToSort
let indexOfReturn = 0;

//count is an array which will be marked in the time complexity
//as k so when you see O(n+k) k is the length(and therefore operations) 
//of count and n is the length(and therefore operations) 
//of the array to be sorted
let count = [];

1. First counting length for() loop

for (i = 0; i <= 9; i++) {
   count[i] = 0;
}

//this for loop sets up the count array to be used to
//keep track of the count of all numbers in the array to be sorted
// => count = [0,0,0,0,0,0,0,0,0,0]
//when created the count array has indexes equal to the base of the
//numbers that you are sorting, and because we are sorting in base 10
//it has 10 indexes that all point to the value zero

1. First array length for() loop

for (i = 0; i < arrayToSort.length; i++) {
   count[arr[i]]++;
}

//this for loop goes for the length of the array that will be
//sorted and increases the value in the indexes of count that are 
//equal to the value in the array that needs to be sorted
// => count = [1,2,1,3,1,1,1,1,1,1]
//the indexes of count now reference the amount of each digit that
//are in the array

1. Second counting length for() loop

for (i = 0; i <= 9; i++) {
   while (count[i]-- > 0) {
      arrayToSort[indexOfReturn++] = i;
   }
}
//this for loop goes for the length of the count and changes the indexes
//of the array to be sorted to be equal to the index of the count array
//while the count is still greater than 0
//You can see that the indexes are not compared against each other but 
//are instead just kept track of through count and returned in index 
//order from smallest to largest from 0 -> 9
// => arrayToSort = [0,1,1,2,3,3,3,4,5,6,7,8,9]

1. Pulling it all together again

countingSort([9,1,0,4,6,5,7,8,1,3,2,3,3])

function countingSort(arrayToSort) {
   let i; 
   let indexOfReturn = 0;
   let count = [];
   for (i = 0; i <= 9; i++) {
      count[i] = 0;
   }
   for (i = 0; i < arrayToSort.length; i++) {
      count[arr[i]]++;
   }
   for (i = 0; i <= 9; i++) {
      while (count[i]-- > 0) {
         arrayToSort[indexOfReturn++] = i;
      }
   }
   return arrayToSort;
}

//output => [0,1,1,2,3,3,3,4,5,6,7,8,9]


// after all the counting and indexing into count is done
//the return is the sorted array

Counting sort doesn't seem too useful but radix sort is built off of counting sorts and both Counting sort and Radix sort have time complexities based off of

// n => Length of the array
// k => Base of the number system you are sorting
// Leading to O ( n + k ) being the runtime

Counting sort has low time complexity because it has limited use, it can only be used on numbers of one character length. It is not a comparison sort so you don't need to know the values of the indexes next to what you are sorting.

References -

https://www.cs.usfca.edu/~galles/visualization/RadixSort.html - Very useful animation about radix sort

https://www.w3resource.com/javascript-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-11.php - Information about how to format a counting sort in javascript