Consider the algorithm given below (see pictures) 5. (12 points) Bucket Sort Con

Question

Consider the algorithm given below (see pictures)

5. (12 points) Bucket Sort Consider the algorithm given If length (A) 15 then list the range of input numbers that will go to each of the buckets 0...14. Bucket 0: Bucket 1: Bucket 2: Bucket 3: Bucket 4: Bucket 5: Bucket 6: Bucket 7 Bucket8: Bucket9: Bucket 10 Bucket 11 Bucket 12 Bucket 13 Bucket 14: Now generalize your answer. If length (A) n then st the range of input numbers that w go to buckets 0,1,... (n-2), (n-1) Bucket 0: Bucket 1: Bucket(n-2): Bucket(n-1):

Explanation / Answer

For length(A)=n there will be 0 to n-1 buckets

And the range of all the numbers present in the array is from X to Y

So in Bucket 0 there will be all the elements whose most significant digit coming in the parition range of each bucket and similar is the case for all other Buckets.

So ith Bucket in the bucket sort algorithm will have k elements in the range of i/10 to (i+1)/10 excluding

example : length(A)=10 & Range of numbers : 0 to 1 A = {0.55 , 0.13 , 0.32 , 0.21 , 0.34 , 0.96 , 0.67 , 0.83 ,0.44 , 0.42 }

Bucket 0 : No Number starting with 0 after decimal so empty bucket

Bucket 1 : 0.13 number starting with digit 1 after decimal

Bucket 2 : 0.21 number starting with digit 2 after decimal

Bucket 3:   0.32 0.34 number starting with digit 3 after decimal

...........So on

Hence each bucket will have numbers in range for ith index bucket is i/10 to (i+1)/10

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.