We say that an array A[1..n] is k-sorted if it can be divided into k blocks,...

 

Transcribed Image Text:

We say that an array A[1..n] is k-sorted if it can be divided into k blocks, each of size n/k, such that the elements in each block are larger than the elements in earlier blocks, and smaller than elements in later blocks. The elements within each block need not be sorted. For example, the following array is 4-sorted: 1 2 4 3 7 6 8 5 10 11 9 12 15 13 16 14 (a) (10 pts) Write down the pseudocode for an algorithm that completely sorts an already k-sorted array of n elements in O(n log(n/k)) time. Write down the pseudocode, analyze its running time and explain why it correctly sorts a k-sorted array. (b) (20 pts) Prove that any comparison-based algorithm to completely sort a k-sorted array requires (n log(n/k)) comparisons in the worst case, i.e., that your algorithm in part (a) is asymptotically optimal? Hint: It is not sufficient to combine lower bounds to sort individual blocks! Think about how many different permutations are possible in a k-sorted array. (c) (OPTIONAL - 0 pts) Prove that any comparison-based algorithm requires at least n(n log k) compar- isons in the worst-case to k-sort an unsorted array of n elements. Can you design an algorithm that k-sorts an unsorted array that runs in O(n log k) time? Activate Windows We say that an array A[1..n] is k-sorted if it can be divided into k blocks, each of size n/k, such that the elements in each block are larger than the elements in earlier blocks, and smaller than elements in later blocks. The elements within each block need not be sorted. For example, the following array is 4-sorted: 1 2 4 3 7 6 8 5 10 11 9 12 15 13 16 14 (a) (10 pts) Write down the pseudocode for an algorithm that completely sorts an already k-sorted array of n elements in O(n log(n/k)) time. Write down the pseudocode, analyze its running time and explain why it correctly sorts a k-sorted array. (b) (20 pts) Prove that any comparison-based algorithm to completely sort a k-sorted array requires (n log(n/k)) comparisons in the worst case, i.e., that your algorithm in part (a) is asymptotically optimal? Hint: It is not sufficient to combine lower bounds to sort individual blocks! Think about how many different permutations are possible in a k-sorted array. (c) (OPTIONAL - 0 pts) Prove that any comparison-based algorithm requires at least n(n log k) compar- isons in the worst-case to k-sort an unsorted array of n elements. Can you design an algorithm that k-sorts an unsorted array that runs in O(n log k) time? Activate Windows

Answer rating: 100% (QA)

a Pseudocode for an algorithm that completely sorts a ksorted array of n elements in Onlognk time Algorithm SortKSortedArrayA n k 1 Divide the array A into k blocks each of size nk 2 Sort each block u... View the full answer