Description
1 K-Sorted Array
We say that an array of distinct integers A[1..n] is k-sorted if for each 1 ≤ i ≤ n,
the i’th smallest element is in positions A[1], …, A[i + k]. Given below is the
pseudocode for sorting a k-sorted array using heap as an auxilary data structure.
Algorithm 1: Sort K-sorted array
Input: A k-sorted array A[1, . . . , n], k
Output: Sorted array of A
1 Initialize array B[1,. . . ,n]
2 S = MakeHeap(A[1], . . . , A[k])
3 for j = k + 1 to n + k do
4 if j ≤ n then
5 Insert(S, A[j])
6 B[j − k] ← ExtractMin(S)
7
8 return B
1
Algorithm 1 uses two auxilary data structures, array B and heap S. It puts
k + 1 elements in heap and extracts minimum from the heap iteratively while
adding a new element from array A into the heap. We want to prove correctness
of the algorithm from this intuition: given that first t elements in array B are
in their ”correct” place, then t + 1th element must also be “correct”.
Work through the following questions to show that this algorithm correctly
sorts the array.
1.1
Make a statement, capturing the above intuition, on the value extracted from
heap at line 6.
1.2
Prove the statement you made in 1.1
1.3
Now using induction on elements of array B, prove the correctness of the algorithm.
2 Inversions
Let A[1 . . . n] be an array of n distinct numbers. If i < j and A[i] > A[j], then
the pair (i, j) is called an inversion of A.
2.1
List the five inversions of the array h2, 3, 8, 6, 1i
2.2
What array with elements from the set {1, 2, . . . , n} has the most inversions?
How many does it have?
2.3
Give an algorithm that determines the number of inversions in any permutation
on n elements in Θ(n log n) worst-case time. (Hint: Modify merge sort.)
2