Last Updated: 21 Dec, 2020
Nearly Sorted
Moderate
Asked in companies
You’re given an array/list 'ARR' of N elements, where each element is at most K away from its target position(Position if the array was sorted). Now, your task is to devise an algorithm that sorts the given array in O(N log K) time.
For example:
Let us consider 'K' is 3, an element at index 4 in the sorted array, can be at indexes 1, 2, 3, 4, 5, 6, 7 in the given array, because the absolute difference of all these indices with 4 is at most 3.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and K, the number of elements in the array and K as specified in the problem statement.
The second line of each test contains N space-separated integers.
Output Format:
The only line of output of each test case should contain N space-separated integers denoting the sorted array.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= K < N <= 5000
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
We will use the Insertion sort to sort the elements efficiently. Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands, where we do the following steps.
- Iterate the array from array[1] to array[n] over the array, where n is the size of the array.
- Compare the current element (key) to its predecessor.
- If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
To sort arrays efficiently, one of the best methods is to use the Heap Data Structure.
- We will start by creating a Min Heap(or a priority queue) of size K+1 with the first K+1 elements.
- We will maintain a priority queue giving priority to the minimum element(min-heap) and we’ll then insert the first K+1 elements of the array in the queue.
- We will run a lop from K+1 till N. We will then start assigning the top element of the queue to the start of the array(we’ll initialize a variable index=0) and then pop this value and also increment the index.
- At the same time, we will push the value at which the current pointer is pointing in the loop(it can be from K+1 to N).
- After this loop terminates, i.e all the elements from the array have been added to the queue. Then, we will just assign the top element of the queue to the array and pop that value. We will do this till the queue is empty.
- Finally, we will print the nearly sorted array.
- Let us understand the working of the above algorithm with the help of an example, where N = 4, K = 2, and the array of size N = 4 is {5,6,2,3}
- We will create a priority queue of size 3(K+1) and insert the first 3 values {5,6,2} in it and also create an integer variable index which is initialized to be 0.
- Then we will run a for loop from 3(K+1) to 4(N) and start assigning the array(from the start of an array using index variable which was initialized to be 0), to have the value of the top of the queue which will return the value of the smallest value from the queue which will be 2. Hence our new array's first element is 2, now we will pop this out of the queue and push a new element in the array which will be 3.
- Now in our case, our loop is terminated as N = 4 has been achieved, so we need not push more elements in the array.
- We’ll keep assigning the top element of the queue to our new array, and pop the top element till the queue becomes empty, and finally print the array.
- After we pushed 3 in our queue, our 2nd element of our new array which is nothing but the top of the queue will be added to the new array and our new array will look like {2,3}.
- Similarly, we’ll add 5 and 6 to our new array and pop them from the queue, and finally now as the queue is empty we’ll just print our new array which is {2,3,5,6}.
We could also use a Balanced Binary Search Tree instead of Heap to store elements as the insert and delete operations on Balanced BST also take O(Logk) time. Hence we can see that a Balanced BST-based method will also take O(N log K) time, but the Heap-based method seems to be more efficient as the minimum element will always be at the root. Also, Heap doesn’t need extra space for left and right pointers. So we will use the Heap Method because of its above-given advantages over the Balanced Binary Search Tree.
Similar problems