Suppose that, instead of sorting an array, we just require that the elements increase on average. More
Question:
Suppose that, instead of sorting an array, we just require that the elements increase on average. More precisely, we call an n-element array A k-sorted if, for all i = 1, 2, . . . ,n ? k, the following holds:
a. What does it mean for an array to be 1-sorted?
b. Give a permutation of the numbers 1, 2, . . . ,10 that is 2-sorted, but not sorted.
c. Prove that an n-element array is k-sorted if and only if A[i] ? A[i + k] for all i = 1, 2, . . . ,n ? k.
d. Give an algorithm that k-sorts an n-element array in O(n lg(n/k)) time. We can also show a lower bound on the time to produce a k-sorted array, when k is a constant.
e. Show that we can sort a k-sorted array of length n in O(n lg k) time.?
f. Show that when k is a constant, k-sorting an n-element array requires ?(n lg n) time.
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest