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 algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

Question

(A) Insertion Sort with time complexity O(kn)
(B) Heap Sort with time complexity O(nLogk)
(C) Quick Sort with time complexity O(kLogk)
(D) Merge Sort with time complexity O(kLogk)
 

what is the approach of doing this question ?

Answer 1

We can perform this in O(nlogK) time using heaps...

First, create a min-heap with first k+1 elements.Now, we are sure that the smallest element will be in this K+1 elements..Now,remove the smallest element from the min-heap(which is the root) and put it in the result array.Next,insert another element from the unsorted array into the mean-heap, now,the second smallest element will be in this..extract it from the mean-heap and continue this until no more elements are in the unsorted array.Next, use simple heap sort for the remaining elements.

Time Complexity---

O(k) to build the initial min-heap

O((n-k)logk) for remaining elements...

Thus we get O(nlogk)

Hence,B is the correct answer

Comments

Well explained :)

---

in choosing the sorting technique.. you have chosen the heapsort as we can add the elements in future from unsorted array?

---

Undoubtedly answer is B)
but i thought (A) is also possibly true please correct me :D

---

Can anyone explain by giving an example for more clarity?

---

@ Nikhil

Yes, (A) is also a possible answer but as we have better answer possible so we have to go with the best one.

Answer 2

Answer is B ,approach is heapify process
Take first k elements and make min. heap by build heap=o (k).
Now delete first min. element from the tree and insert next element from the array and again heapify ....and repeat same thing.
So total complexity
K+{log k +log k +log  k. ......(n-1) times }
=n(ogk)