1,032 views
0 votes
0 votes

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?

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)

Answer given is B, and i somewhat get the resoning behind it,but one thing which i can not understand is why can't we follow same resoning even if this information that every element is distant by k units is not given?

The resoning is :

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.

Pls provide your explantion

1 Answer

0 votes
0 votes

if this information that every element is distant by k units is not given?

In this case we would not be having an idea that how far we have to check, that means we have to check in the complete array.

So what we have to do in this case is, Build heap with size n which will take O(n) and then we have to delete one by one and as you know that the deletion will take O(log n). we have to apply the delete operation for each element in the heap i.e n time logn

So finally it will take O(nlogn).

Related questions

3 votes
3 votes
1 answer
1
1 votes
1 votes
1 answer
2
Tauhin Gangwar asked Feb 5, 2017
540 views
Is this grammar is left factored if yes ??? plz explain how