You are given an array of n elements such that each element is at max k place away from its original sorted position, you have to sort the array in the correct manner.
The problem asks you to sort the array in minimum possible time, the main catch here is how to use the information that the elements are at maximum k place away from its original sorted position.
The first line of the input consists of T number of test cases, each test case consists of N size of the array following line consist of N numbers as the input of the array.
You are required to print the sorted form of the array.
Input: T=1 N=4 2 3 1 2 4 Output: 1 2 3 4 Since 3 original position is at index 0 but in the sorted array it should be at index 2, 1 should be at index 0 and 2 should bet at index 1 therefore maximum distance between the current position and sorted position is 2 therefore it can be solved with the help of heap. Input: T=1 N=6 K=4 4 3 2 1 5 6 Output: 1 2 3 4 5 6 Similarly, as the previous case the maximum difference between original index and current position is 3 for element 4 indexed at 0.
The problem asks you to solve it in an efficient manner since it is possible to sort the array with the help of insertion sort method which will take O(n*k) time since we have a total of a number of elements and each element can be at max k place away from its original position. So to avoid that time complexity we will use the heap data structure:
The overall time complexity for the above approach in the worst case is: O(nlog(k))
Space complexity for the above approach in worst case i: O(k+1)
C++ Implementation (Heap Approach):