Count sort in C

Count sort in C C++

Count sort is index based sorting algorithm. It is much faster than comparison based sorting technique but takes a lot more space.

Explanation

We initialise an array T with of size equal to the 1 + greatest element in the list/array A that needs to be sorted and set value of all elements of T as 0 initially.

Now loop/iterate through our main array A and increment the element of array T at index equal to the element of array A . Like first element is 6 so increment element at index 6 of the array T.

So we obtain the following array T.

Now loop/iterate through this array T, and if the element has value greater that 0, assign that index to the array A and decrement the value at that index of array T.

Like in array T, at index 3 value is 2, that is, greater than 0 so assign value 2 to the first element of our main array A and then decrement the value 2 to 1. Iterate further and assign the next obtained value to 2nd element of A and continue.

Final outcome

Time complexity of count sort is O(n).

Other sorting algorithms

Merge sort in C/C++

Quick Sort in C/C++

Selection sort in C/C++

Insertion Sort in C/C++

Bubble Sort in C/C++

Criteria for sorting analysis