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,\dots ,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,\dots ,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,\dots ,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. ($\mathit{\text{Hint:}}$ Use the solution to Exercise 6.5-9.)

f. Show that when $k$ is a constant, $k$-sorting an $n$-element array requires $\mathrm{\Omega }(n\lg n)$ time. ($\mathit{\text{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 $\mathrm{\Omega }(n/k\lg (n/k))$, so the total lower bound is $\mathrm{\Theta }(n\lg (n/k))$. Since $k$ is a constant, therefore $\mathrm{\Theta }(n\lg (n/k))=\mathrm{\Omega }(n\lg n)$.

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