Question

Illustrate the operation of counting sort on the array A = (3, 5, 7, 2, 4, 3, 5, 8, 1). Show the contents of the array C after the completion of steps 3 and 4, and again after the completion of steps 5 and 6. Show the contents of arrays B and C after each iteration of steps 7, 8, and 9.

Answer 1

See explanation

Explanation:

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Let us understand it with the help of an example.

For simplicity, consider the data in the range 0 to 9.

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

1) Take a count array to store the count of each unique object.

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

Count: 0 2 2 0 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 4 4 5 6 6 7 7 7

The modified count array indicates the position of each object in

the output sequence.

Answer 2

Explanation:

Array, A = (3, 5, 7, 2, 4, 3, 5, 8, 1)

By sorting array A = (1, 2, 3, 3, 4, 5, 5, 7, 8)

n = 9:

Let K, be the range of non-negative value

K = 8 - 1 = 7

Array, B = (7, 2, 4, 3, 5, 8, 1)

By sorting array B = (1, 2, 3, 4, 5, 8)

n = 7

K = 8 -1 = 7

a) Array, C after step 3 and 4 = (4, 3, 5, 8, 1)

By sorting array C = (1, 3, 4, 5, 8)

n = 5

Array, C after step 5 and 6 = (5, 8, 1)

By sorting array C = (1, 5, 8)

c) Arrays, B = (1, 2, 3, 4, 5, 8) and C = (1, 5, 8)

Both have the same K = 8 - 1 = 7