3. Let S be a sequence containing pairs (k,e) where e is an element and k is its
ID: 3908946 • Letter: 3
Question
3. Let S be a sequence containing pairs (k,e) where e is an element and k is its key. There is a simple algorithm called count-sort that will construct a new sorted sequence from S provided that all the keys in S are different from each other. For each key k, count-sort scans S to count how many keys are less than k. If c is the count for k then (k, e) should have rank c in the sorted sequence. (a) (5 points) Give the pseudocode for count-sort as it is described above. (b) (3 points) Determine the number of comparisons made by count-sort. What is its running time? (c) (2 points) As written, count-sort only works if all of the keys have different values. Explain how to modify count-sort to work if multiple keys have the same value.Explanation / Answer
a)
CountSort(Sequence[]):
Input the sequence of n elements(k,e)
Initialize space for sorted sequence
sortedsequence[n]
for loop i: 1..n
do
count = 0 //Initialize the number of elelements smaller than Sequence[i]
for loop j:1 to n // Traversing the loop to find out how many numbers are smaller than Sequence[i]
if i != j and Sequence[i].k > Sequence[j].k
count = count + 1 // Increment the count
loop end
sortedsequence[count] = Sequence[i] // Store the element at the appropriate position in the sorted sequence
loop ends
Output sortedsequence[n]
b) Comparisons for every element is n. The complexity is O(n^2)
c) Multiple key having same value:
CountSort(Sequence[]):
Input the sequence of n elements(k,e)
Initialize space for sorted sequence
sortedsequence[n]
for loop i: 1..n
do
count = 0 //Initialize the number of elelements smaller than Sequence[i]
for loop j:1 to n // Traversing the loop to find out how many numbers are smaller than Sequence[i]
if i != j and Sequence[i].k >= Sequence[j].k
count = count + 1 // Increment the count
loop end
sortedsequence[count] = Sequence[i] // Store the element at the appropriate position in the sorted sequence
delete(Sequenc[i]) // delete the ith element of the sequence.
loop ends
Output sortedsequence[n]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.