Divide and Conquer

Question

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algo can be easily modified for sorting this array and what is the obtainable time complexity ?

Answer 1

We can use heap sort in a different way.

Create a min heap of first k elements. Now, since we know that the smallest element will be among the first k elements, we can get it by extracting the minimum from the heap created. Now, after removing it, add the next element (i.e k+1)th to the min heap. And keep repeating this process.

ANALYSIS:

1. Creating a min-heap of k elements = O(k)

2. Extracting min n times -> O(nlogk)

3. Adding (n-k) elements into the heap one by one -> O((n-k)logk) -> O(nlogk)

So, overall time complexity will be: O(k + nlogk), i.e O(nlogk) when k is small compared to n

see this for reference: http://www.geeksforgeeks.org/nearly-sorted-algorithm/