The count of an element will be stored as - Suppose array element '4' is appeared two times, so the count of element 4 is 2.
Now, we have to store the count of each array element at their corresponding index in the count array. This array will be used to store the count of the elements in the given array.ģ. Now, initialize array of length max + 1 having all 0 elements. Find the maximum element from the given array. It will be easier to understand the counting sort via an example.ġ. To understand the working of the counting sort algorithm, let's take an unsorted array. Now, let's see the working of the counting sort Algorithm. Now, find the cumulative sum and store it in count arrayĭecrease the count of every restored element by 1 Store that count at ith position in the count array Max = find maximum element in the given arrayįind the count of every unique element and Perhaps a trade off considering my example has slightly “worse” space complexity, but it’s fun to try different things.CountingSort(array, n) // 'n' is the size of array My variation allows for inputting only an Array of integers, and does not have nested loops. Two commonalities that I’ve noticed in other examples are 1) the need to know the minimum and maximum values to include as input, and 2) the use of a while loop nested within a for loop. It’s possibly not the best one, but it works and is rudimentary, understandable. There are numerous variations of the counting sort algorithm. It’s simpler to think of k, the range, as the maximum value of the input. Note that the specific time complexity of counting sort is O(n + k), wherein n is the length of the input, and k is the range of the input. I presume an acceptable maximum value is circumstantial, but once large numbers ( 1000+?) enter the mix, consider an alternative algorithm. The need to create an auxiliary Array comes at the cost of space, and if the maximum input value is great, then the space complexity of the algorithm would make it inefficient and, therefore, unusable. This condition requires that the maximum value of the integers being sorted is a relatively small number. input => 5 1 3 count Array => idx 0 1 2 3 4 5 _ arr
COUNTING SORTY PLUS
For example, if the input was the sequence 5 1 3, the count Array would need to accommodate an index 5, plus an additional element to represent the index 0. It is done by initializing an Array of 0s to accommodate the maximum input value. It is in the form of an auxiliary Array which stores the frequency count, i.e. Caveat #2: Lesser ValuesĪs the name suggests, counting sort utilizes a counting procedure. This requires a condition wherein the objects-the elements, or values-being sorted are exclusively integers, and, since they must be able to represent an Array index, they must be 0 or greater. The sorting is performed by using values concurrently as keys and indices. Unlike most other sorting algorithms, counting sort is not a comparison sort. * Note: linear time sorting can also be achieved with the best case scenario bucket sort (which is not a proper evaluation-time complexity considers the worst case scenario) and radix sort, which itself utilizes counting sort as a sub-routine. If the conditions allow, and time efficiency is a priority, counting sort can shine. Counting sort provides a rarely useable, but more performant algorithm. Most sorting algorithms perform in quadratic time ( O(n²)), and the two exceptions-heap and merge-maximize efficiency at linearithmic time ( O(n log n)). However, if the stars align and the conditions are just right, counting sort offers a unique advantage: it is the only sorting algorithm which performs in linear time ( O(n)). Have you ever heard of it? It is infrequently used because it comes with some caveats which make it impractical in most use cases. There is also a lesser known sorting algorithm, relegated to the proverbial annex like poor Toby: counting sort. bubble, quick, selection, insertion, merge, heap, bucket. There are several well known sorting algorithms: e.g. In computer programming-and mathematics, for that matter-sorting algorithms are frequently used to order data as needed to perform a calculation, feed an engine, render an interface, etc. It makes sense to organize things to better use them.
Sorting is a near ubiquitous process in our daily lives.