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.

$$ \begin{aligned} \frac{\sum_{j = i}^{i + k - 1} A[j]}{k} & \le \frac{\sum_{j = i + 1}^{i + k}A[j]}{k} \\ \sum_{j = i}^{i + k- 1 } A[j] & \le \sum_{j = i + 1}^{i + k} A[j] \\ A[i] & \le A[i + k]. \end{aligned} $$

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)$.