Suppose that we are given a sequence A of n positive real numbers (a, a2,.., an)...

  

Transcribed Image Text:

Suppose that we are given a sequence A of n positive real numbers (a, a2,.., an) to sort. a) (2 points) Can you use Count Sort AS IS to sort A? Explain b) (28 points) How can you adapt Counting Sort to sort the sequence A? Clearly state your assumptions and describe clearly using pseudocode your new Counting Sort algorithm COUNTING-SORT (A, B, k) 1 2 3 4 5 6 7 8 9 10 11 12 let C[0..k] be a new array for i 0 to k C[i] = 0 for j 1 to A.length C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i. for i=1 to k C[i] = C[i] + C [i 1] // C[i] now contains the number of elements less than or equal to i. for j = A.length downto 1 B[C[A[j]]]= A[j] = C[A[j]] = C[A[j]] - 1 Suppose that we are given a sequence A of n positive real numbers (a, a2,.., an) to sort. a) (2 points) Can you use Count Sort AS IS to sort A? Explain b) (28 points) How can you adapt Counting Sort to sort the sequence A? Clearly state your assumptions and describe clearly using pseudocode your new Counting Sort algorithm COUNTING-SORT (A, B, k) 1 2 3 4 5 6 7 8 9 10 11 12 let C[0..k] be a new array for i 0 to k C[i] = 0 for j 1 to A.length C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i. for i=1 to k C[i] = C[i] + C [i 1] // C[i] now contains the number of elements less than or equal to i. for j = A.length downto 1 B[C[A[j]]]= A[j] = C[A[j]] = C[A[j]] - 1

Answer rating: 100% (QA)

The given pseudocode represents the Counting Sort algorithm Counting Sort is a noncomparisonbased so... View the full answer