We say that an array A[1 · · · n] is k-sorted if it can be divided into k blocks
ID: 3571994 • Letter: W
Question
We say that an array A[1 · · · n] is k-sorted if it can be divided into k blocks, each of size n/k, such that the elements in each block are larger than the elements in earlier blocks, and smaller than elements in later blocks. The elements within each block need not be sorted.
For example, the following array is 4-sorted: [1, 2, 4, 3||7, 6, 8, 5||10, 11, 9, 12||15, 13, 16, 14]
a. Describe an algorithm that k-sorts an arbitrary array in O(n log k) time. (You should provide an algorithm and analyze its complexity. HINT: think about the quick-sort)
b. Use the decision tree method to prove that any comparison-based k-sorting algorithm requires (n log k) comparisons in the worst case. (HINT: count the number of possible outcomes of any k-sorting algorithm. Use the Stirling’s approximation log(n!) n log n n. )
Explanation / Answer
void insertionSort(int A[], int size)
{
int i, key, j;
for (i = 1; i < size; i++)
{
key = A[i];
j = i-1;
/* Move elements of A[0..i-1], that are greater than key, to one
position ahead of their current position.
This loop will run at most k times */
while (j >= 0 && A[j] > key)
{
A[j+1] = A[j];
j = j-1;
}
A[j+1] = key;
}
}
The inner loop will run at most k times. To move every element to its correct place, at most k elements need to be moved. So overall complexity will be O(nk)
We can sort such arrays more efficiently with the help of Heap data structure. Following is the detailed process that uses Heap.
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time (See this GFact)
2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.
Removing an element and adding a new element to min heap will take Logk time. So overall complexity will be O(k) + O((n-k)*logK)
#include<iostream>
void swap(int *x, int *y);
class Heap3
{
int *harr; // pointer to array of elements in heap
int heap_size; // size of min heap
public:
// Constructor
Heap3(int a[], int size);
// to heapify a subtree with root at given index
void Heap3ify(int );
// to get index of left child of node at index i
int left(int i) { return (2*i + 1); }
// to get index of right child of node at index i
int right(int i) { return (2*i + 2); }
int replaceMin(int x);
int extractMin();
};
int sortK(int arr[], int n, int k)
{
// Create a Min Heap of first (k+1) elements from
// input array
int *harr = new int[k+1];
for (int i = 0; i<=k && i<n; i++) // i < n condition is needed when k > n
harr[i] = arr[i];
Heap3 hp(harr, k+1);
// i is index for remaining elements in arr[] and ti
// is target index of for cuurent minimum element in
// Min Heapm 'hp'.
for(int i = k+1, ti = 0; ti < n; i++, ti++)
{
// If there are remaining elements, then place
// root of heap at target index and add arr[i]
// to Min Heap
if (i < n)
arr[ti] = hp.replaceMin(arr[i]);
// Otherwise place root at its target index and
// reduce heap size
else
arr[ti] = hp.extractMin();
}
}
Heap3::Heap3(int a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1)/2;
while (i >= 0)
{
Heap3ify(i);
i--;
}
}
// Method to remove minimum element (or root) from min heap
int Heap3::extractMin()
{
int root = harr[0];
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
heap_size--;
Heap3ify(0);
}
return root;
}
// Method to change root with given value x, and return the old root
int Heap3::replaceMin(int x)
{
int root = harr[0];
harr[0] = x;
if (root < x)
Heap3ify(0);
return root;
}
void Heap3::Heap3ify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
Heap3ify(smallest);
}
}
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void printArray(int arr[], int size)
{
for (int i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver program to test above functions
int main()
{
int k = 3;
int arr[] = {5, 6, 3, 12, 46, 7};
int n = sizeof(arr)/sizeof(arr[0]);
sortK(arr, n, k);
cout << "Following is sorted array ";
printArray (arr, n);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.