Suppose you are given the task of sorting n = 1000, 32 bit binary keys. You have decided to use radix sort (which uses counting sort as a stable sorting algorithm subroutine) for this problem but you are unsure whether to use counting sort on each bit separately or whether to use counting sort on groups of bits to minimize the total running time. You want to find out whether it is best to assign 1,4,8 or 16 bits per group and perform to the counting sort on each group. You are provided with a counting sort procedure that sorts n numbers (each numbers taking value in the range {0, . . . , k}) with exact time complexity of 5n + 4k. Find the exact runtime of the following four cases by filling out the following table and justifying your answer

(a) Use 1 bit/per group and call counting sort subroutine for each group.

(b) Use 4 bit/per group and call counting sort subroutine for each group.

(c) Use 8 bit/per group and call counting sort subroutine for each group.

(d) Use 16 bit/per group and call counting sort subroutine for each group.

(e) Which of the above three options is preferable? Explain why

Transcribed Image Text:

part (a) part (b) part (c) part (d) # possible values #bits/groups# group (d) per group (k) Countingsort time per group Radix sort time i.e., Counting sort time in total (for all groups) part (a) part (b) part (c) part (d) # possible values #bits/groups# group (d) per group (k) Countingsort time per group Radix sort time i.e., Counting sort time in total (for all groups)

Answer rating: 100% (QA)

To determine which option is preferable in terms of runtime well calculate the exact runtime for eac... View the full answer