2 Consider the following algorithm to sort an array Apply th

2. Consider the following algorithm to sort an array:      

Apply the algorithm to sort the list 7, 3, 5. In other words, assume that the array A[ ] has the initial values 7, 3, and 5. Present the contents of the arrays A[ ], S[ ], and Count [ ] after finishing the execution of the algorithm.

Similarly, present the contents of the three arrays if the array A[ ] has the initial values 9, 3, 3, 9, 3, 6?

Is the algorithm stable? Example your answer.

Algorithm ComparisonCounting Sort (A10 -1 S 0..1n 1 Sorts an array by comparison counting Input: Array Al0..n 11 of orderable values Output: Array S 0..n 1 of A\'s elements sorted in nondecreasing order for 0 to n 1 do Count 0 for 0 to n 2 do for j i 1 to n 1 do if Ali] Ali) Count Count 1 else Count i Count i 1 for 0 to n 1 do Count il Ali

Solution

1. Assume A has [7,3,5] , Initailly Count [0,0,0] and S[]

After the algorithm executes
A [7,3,5]
Count[2,0,1]    // 7 is greater than both the elements so count is 2 in 7 place, similarly for 3 (0) and 5 (1)
S[3,5,7]

b ) Assume A has [9,3,3,9,3,6] , Initailly Count [0,0,0,0,0,0] and S[]

After the algorithm executes
A [9,3,3,9,3,6]
Count[4,0,1,5,2,3]  
S[3,3,3,6,9,9]

The algorithm is stable because it keeps the order of places if the elements are same.
For example A[9,9]
Output is [9,9] .. But they have not swapped position i,e relative ordering is still same.