8-5

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....n k, the following holds:

$$ \frac{\sum_{j=i}^{i+k-1} A[j]} {k} \leq \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...,10 that is 2-sorted, but not sorted. c. Prove that an n-element array is k-sorted if and only if $A[i] \leq 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. (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. (Hint: Use the solution to the previous part along with the lower bound on comparison sorts.)
a. It is sorted.c has the answer for this puzzle for 1 sorted the it should satisfy $A[i] \leq A[i + 1]$ . hence the i+1 should always be greater than ith element where i is from 1..n.
b. Any permuatation that violates $A[i] \leq A[i+2]$ will work. ex: 1 3 2 4 5 6 7 8 9 10.
c. from the inequality for k - sorted array. $$ \sum_{j=i}^i+k-1 A[j] \over k \leq \sum_{j=i+1}^i+k A[j]$$ cancelling k on both sides $$ \sum_{j=i}^i+k-1 A[j] \leq \sum_{j=i+1}^i+k A[j]$$ expanding summation $$ A[i]+...+A[i+k-1] \leq A[i+1]+..+A[i+k]$$ cancelling elements from A[i+1] to A[i+k-1] $$ A[i] \leq A[i+k]$$ d. if we split the array in to groups of n/k and sort each group of n/k elements using any comparison sort the running time is $O(n/k log n/k )$. but since we do it for k times the running time is $O(k.n/k. log n/k$ = $O(n log n/k )$ e. If we sort the array using d algorithm and we have k sorted list we build MIN-HEAP on first k elements and EXTRACT-MIN-HEAP and repeat this for n/k times the running time is O(n log k). f. we can use the decision tree for calculating the lower bound. The leaves of the decision tree are various permutations of k-sorted array. $$ {{n} \choose {k}} . {{n-k} \choose {k}} . {{n-2k} \choose {k}}..{{k} \choose {k}} $$ $$ n!/k!(n-k)! . (n-k)!/(n-2k!).k! . (n-2k)!/(n-3k)! k! ..... k!/0! k! $$ $$ n!/ {k!}^{n/k} $$ since it is binary the no of leaves at height h is $$ 2^h \geq n!/ {k!}^{n/k} $$ if k were a constant lets replace k with c $$ 2^h \geq n!/ c $$ applying log $$ h \geq log( n!/ c) $$ $$ h \geq log( n!)- log c $$ log c should be negative $$log c < 0$$ $$ c < 1$$ $$ h \geq n log( n)$$