If you are using divide and conquer to solve the problems, then your solution mu

Question

If you are using divide and conquer to solve the problems, then your solution must clearly and specify describe each of the following steps:

• Dividing the problem into sub problems

• Solving sub problems

• Merging solutions of sub problems.

Then, you must derive a recurrence relation for the run-time of the algorithm, and solve the recurrence relation. In this PA, you may assume that n is a power of 2 (if it helps).

An array of integers [a1, a2, · · · , an] is k-sorted if the following condition holds: For every i, 1 i n k, a[i] a[i + k]. Design an algorithm that gets a k-sorted array as input and sorts it. Describe your algorithm and derive the run time. Express runtime in terms of n and k. Your grade partly depends on the efficiency of your algorithm.

Explanation / Answer

Please find my algorithm:

Algorithm:

Since array is k-sorted means each element is at most k away from its target position, we can use HEAP to sort entire whole array efficiently.

Algorithm:
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time
2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.

Time Complexity:
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)

PsudoCode:
int sortKArray(int arr[], int n, int k)
{
// Create a Min Heap of first (k+1) elements from
// input array
int harr[k+1];
for (int i = 0; i<=k && i<n; i++) // i < n condition is needed when k > n
harr[i] = arr[i];
// create min heap
MinHeap 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();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.