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)Correct answer is option 'B'. Can you explain this answer?

Question

Answer

Explanation:

The given array has the property that every element in the array is at most k distance from its position in the sorted array, where k is a positive integer smaller than the size of the array. This property is called k-sorted array. We need to sort this k-sorted array. To sort this array, we can use Heap Sort.

Heap Sort:

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. In Heap Sort, the array is first converted into a binary heap, and then the root element is removed and placed at the end of the array. This process is repeated until the entire array is sorted.

Modifying Heap Sort for k-sorted array:

To sort a k-sorted array using Heap Sort, we can use a min-heap of size k+1. We first build a min-heap of the first k+1 elements of the array. Then, we remove the minimum element from the heap and insert the next element from the array into the heap. We repeat this process until all the elements are processed.

Time Complexity:

The time complexity of Heap Sort for a k-sorted array is O(nLogk), where n is the size of the array. This is because we are processing each element of the array once and each insertion and removal from the heap takes O(Logk) time.

Conclusion:

Thus, we can use Heap Sort to sort a k-sorted array with a time complexity of O(nLogk).

Answer

[this answer assumes we are sorting the array in ascending order, using analogy, we can write an explanation for sorting the array in descending order as well]

We are given an unsorted array and we have to create a sorted one. Let us find the elements of the sorted array one-by-one, and also calculate how much work we are doing in finding these elements.

Let us first begin by finding the first element of the sorted array. How can we do this? We know that the first element in the sorted array will be among the first (k+1) elements of the unsorted array (recall that each element is at most k distance away from its correct position). Let us create a min-heap of these (k+1) elements. Now, if we perform extract-min operation on this heap, we get the smallest element among these (k+1) elements, and thus, we have got the first element of the sorted array.

How much work have we done so far? Heap creation of k+1 elements costs O(k) and extract-min on the heap costs O(log k).

Now, to get the second element of the sorted array, we know that it is the second smallest element among the first (k+2) elements of the unsorted sorted array. Since we already have a heap of the first (k+1) elements, we insert the (k+2)th element to the heap. The heap now has k+1 elements (how? K+1 initial elements - 1 (extract min) + 1 (insertion)). Since we have already extracted the smallest element from the heap, performing one extract-min now will give us the second smallest element. Hence, we get the second element of the sorted array. How much work did we do for getting the second element? One insertion and one extract-min, both O(log k).

Likewise, to get the third element, we insert the (k+3)th element to the heap and then do an extract-min. Again, the cost of these operations will be O(log k).

We see that, after we have got (i-1) elements of the sorted array, to get the i th element, we insert (k+I) th element to the heap and then perform extract min, and it costs us O(log k).

To get n elements, we spend O(n log k), hence we have modified heap sort to cost us O (n log k). Note that we also spent O(k) initially in building the first heap of (k+1) elements, but since k is less than n, the O(n log k) function dominates over O(k) and hence we can just report O(n log k) as answer omitting the O(k) term.

Similar Computer Science Engineering (CSE) Doubts

Which of the following is not true about comparison based sorting algorithms?

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company