Question

Sort the numbers: 2, 1, 4, 5, 7, 1, 7, 11, 8, 9 using the counting sort.

Answer 1

COUNTING SORT ALGORITHM:

Counting Sort Algorithm is an efficient and stable sorting algorithm that can be used for sorting elements within a specific range. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.

Let us consider an example and the data in the range 0 to 9

Input data: 1,5,1,3,7,4,3

1)Take a count array for storing the count of each unique element

INDEX: 0 1 2 3 4 5 6 7 8 9

COUNT: 0 2 0 2 1 1 0 1 0 0

2)Modify the count array such that each element at each index stores the sum of previous counts

INDEX: 0 1 2 3 4 5 6 7 8 9

COUNT: 0 2 2 4 5 6 6 7 7 7

The modified count array indicates the position of each object in the output sequence

3)Output each object from the input sequence followed by decreasing its count by 1.

Process the input data : 1,5,1,3,7,4,3. Position of 1 is 2.Put data 1 at output with index 2. Decrease count by 1 to place next data 1 at an index 1 smaller than this index.

Now for the given elements 2,1,4,5,7,1,7,11,8,9

STEP 1:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11  

COUNT: 0 2 1 0 1 1 0 2 1 1 0 1

STEP 2:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 2 3 3 4 5 5 7 8 9 9 10

STEP 3:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 2 3 3 4 5 5 7 8 9 9 10

PLACES:

1 2 3 4 5 6 7 8 9 10

2

STEP 4:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 2 2 3 4 5 5 7 8 9 9 10

PLACES:

1 2 3 4 5 6 7 8 9 10

1 2

STEP 5:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 1 2 3 4 5 5 7 8 9 9 10

PLACES:

1 2 3 4 5 6 7 8 9 10

1 2 4

STEP 6:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 1 2 3 3 5 5 7 8 9 9 10

PLACES:

1 2 3 4 5 6 7 8 9 10

1 2 4 5

STEP 7:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 1 2 3 3 4 5 7 8 9 9 10

PLACES:

1 2 3 4 5 6 7 8 9 10

1 2 4 5 7

STEP 8:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 1 2 3 3 4 5 6 8 9 9 10

PLACES:

1 2 3 4 5 6 7 8 9 10

1 1 2 4 5 7

STEP 9:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 1 2 3 3 4 5 6 8 9 9 10

PLACES:

1 2 3 4 5 6 7 8 9 10

1 1 2 4 5 7 7

STEP 10:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 0 2 3 3 4 5 5 8 9 9 10

PLACES:

1 2 3 4 5 6 7 8 9 10

1 1 2 4 5 7 7 11

STEP 11:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 0 2 3 3 4 5 5 8 9 9 9

PLACES:

1 2 3 4 5 6 7 8 9 10

1 1 2 4 5 7 7 8 11

STEP 12:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 0 2 3 3 4 5 5 7 9 9 9

PLACES:

1 2 3 4 5 6 7 8 9 10

1 1 2 4 5 7 7 8 9   11

STEP 13:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11

COUNT: 0 0 2 3 3 4 5 5 7 8 9 9

PLACES:

1 2 3 4 5 6 7 8 9 10

1 1 2 4 5 7 7 8 9   11

Therefore, the sorted elements for the given input are:

1,1,2,4,5,7,7,8,9,11