Simple Counting Sort
Tags: sort, counting
Published: 2019-07-25 17:35:59


Sorting data takes time.
![](https://thepracticaldev.s3.amazonaws.com/i/wngjjit2009w3b96d4la.jpg)

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?

```javascript
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

```javascript
//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 = [];

```

2. First counting length for() loop

```javascript
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
```

3. First array length for() loop


```javascript
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
```

4. Second counting length for() loop

```javascript
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]
```

5. Pulling it all together again

```javascript
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 

```javascript

// 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