8-5 Average sorting

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, \ldots, n - k\), the following holds:

\[\frac{\sum_{j = i}^{i + k - 1} A[j]}{k} \le \frac{\sum_{j = i + 1}^{i + k} A[j]}{k}.\]

a. What does it mean for an array to be \(1\)-sorted?

b. Give a permutation of the numbers \(1, 2, \ldots, 10\) that is \(2\)-sorted, but not sorted.

c. Prove that an \(n\)-element array is \(k\)-sorted if and only if \(A[i] \le A[i + k]\) for all \(i = 1, 2, \ldots, 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. (\(\textit{Hint:}\) Use the solution to Exercise 6.5-9.)

f. Show that when \(k\) is a constant, \(k\)-sorting an \(n\)-element array requires \(\Omega(n\lg n)\) time. (\(\textit{Hint:}\) Use the solution to the previous part along with the lower bound on comparison sorts.)

a. Ordinary sorting

b. \(2, 1, 4, 3, 6, 5, 8, 7, 10, 9\).

c.

d. Shell-Sort, i.e., We split the \(n\)-element array into \(k\) part. For each part, we use Insertion-Sort (or Quicksort) to sort in \(O(n / k \lg(n / k))\) time. Therefore, the total running time is \(k \cdot O(n / k \lg(n / k)) = O(n\lg(n / k))\).

e. Using a heap, we can sort a \(k\)-sorted array of length \(n\) in \(O(n\lg k)\) time. (The height of the heap is \(\lg k\), the solution to Exercise 6.5-9.)

f. The lower bound of sorting each part is \(\Omega(n / k\lg(n / k))\), so the total lower bound is \(\Theta(n\lg (n/k))\). Since \(k\) is a constant, therefore \(\Theta(n\lg(n / k)) = \Omega(n\lg n)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用