Counting Sort in Data Structure

Counting sort Algorithm was created by Harold H Seward in 1954.
It takes the advantage of knowing the range of numbers in the array to be sorted.
It assume that each of the n input elements is n integer in the range 1 to k, for some integer k.
where K = O (n) the sort runs in O (n) time.
It is a stable sort technique.
In this sort same number in the sequence does not change .

For Example:

Number should preserve its position at the time of comparison if they are same.

Table of Contents

Counting Sort Algorithm pseudocode

Let Array A [1…………….n] contains input sequence where one entry in this array that is A[j] belongs { 0,1,……K} and i = 0,1,……… n where n is the largest element in the array.
The array C [ $k_{1}……………………..k_{n}$] is used for auxiliary storage where $k_{1}$ and [ $k_{n}$ are minimum and maximum key value in the given input sequence.
The array B [ 1…………………..n] is used to hold the sorted out.
Each index (i) in array c used to count how many elements in A have the (i). The elements sorted in C array used to put the elements in a into their write position in the resulting array B.
This procedure takes $\theta (k+n) $ time to run.
The counting sort beats the lower bound $\Omega ( n log n) because it not a comparison based sorting there is no comparison between elements counting sort uses the actual values of the elements in index into an array.

Question: Illustrate the operation of Counting Sort on the array A=(6,0,2,0,1,3,4,6,1,3,2)

Answer:

Here K=6 (highest number in A)

For i = 0 to 6

c[i] = 0

i.e,

for j $\gets$ 1 to 11

for i =1 to 6

Thus, the final Sorted Array is B

Subscribe to get the latest posts sent to your email.