CS29003 Algorithms Laboratory |
Autumn 2013, L-T-P: 0-0-3 |

## Assignment No 7

## Inline Counting Sort

Implement the counting sort algorithm taught in the class with two variations:

- The entries in the input array
Aare now allowed to be integer values in the range −kto +k.- You are not allowed to use the output array
B. Use the count arrayC, and in the final pass through the arrayA, modifyAitself so thatAis sorted inline. This version of counting sort need not be stable.Notice that once you prepare the count array, you may think about printing the integers −

k, −k+ 1, −k+ 2,...,k− 1,kin that sequence the required numbers of times. In practice, however, you sort a record of items with respect to some key value. Therefore, this flat listing of only the key values is not treated as sortingA. Use suitable swap operations to effect inline sorting. The running time of the inline sorting should continue to remain O(n+k).Write a program to do the following.

- Write a function that takes as input the array
A, its sizen, and the limit. The function sortsAaccording to the inline counting sort algorithm.- Write a main() function that reads
nandkfrom the user. It then creates a random arrayAwithninteger entries each in the range −k to +k. It calls the above function to sortA. The arrayAis printed before and after sorting.## Sample Output

n = 100 k = 10 +++ The array before sorting 4 0 -1 6 -3 3 -3 6 7 8 4 10 -5 2 0 -5 1 -9 1 2 9 -10 4 -10 1 -1 6 4 -3 -1 -8 1 0 10 -2 1 2 -10 4 5 4 -9 -4 -7 7 -6 5 1 -5 -4 9 5 3 -6 -9 0 -3 -9 6 10 1 -4 -9 -9 -5 9 -5 2 -3 4 5 2 8 -1 2 -3 2 10 2 -1 7 -7 10 -8 3 -3 0 -1 -2 9 -8 -5 6 -8 9 -1 5 4 3 -6 +++ The array after sorting -10 -10 -10 -9 -9 -9 -9 -9 -9 -8 -8 -8 -8 -7 -7 -6 -6 -6 -5 -5 -5 -5 -5 -5 -4 -4 -4 -3 -3 -3 -3 -3 -3 -3 -2 -2 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 8 8 9 9 9 9 9 10 10 10 10 10

## Submission site | Miscellaneous information | Home