Sort a K Sorted Array

Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time.

Examples:
Input : arr[] = {6, 5, 3, 2, 8, 10, 9}, k = 3
Output : arr[] = {2, 3, 5, 6, 8, 9, 10}

Thought Process

Lets try to understand the problem, Each element is at most k away from its target position means that the element at index 3rd can be place at 0th, 1th, 2th index or can also be place at 4th, 5th, 6th index. Here, k is 3.

In the above above diagram we have visualized it for the 3rd index element. Now its time to visualize it for all the elements in the array. We have to check the possibility of the element at each index. In the below diagram, we can see that for each index we have to select the element from this bunch of elements.

For eg, at 0th index, there is possibility that 6 or 5 or 3 or 2 can be placed.
Are you seeing any pattern in it? In very first time, we have to grab first (k+1) elements (here k is 3) and find the smallest in it and place that number at that index and then for next index pick (k+2)th element and find smallest in it and so on.

Below is the visualization.
Consider k=3

For 0th index, we have to choose the smallest element among all possible elements. So, we choose ‘2’. Now, when we choose ‘2’ there is no any possibility that it can be choose further in the array. Same goes for every element.

Brute Force

Make an array of first (k+1) elements and sort it. Extract the first element, print it and delete it from the array and add the next element i.e. (k+2)th element, again sort it, print it and delete it. We have to do it till the end of the array.
Sorting at every index takes O(k * log k) and moving all the elements to left after deleting first element takes O(k). For whole array of n elements, it takes n * O(k log k +O (k))

Using Heap

Can you think of a data structure from where we can extract the min element in constant time? Yes, binary min-heap.
It takes O(log k) time to insert any element in heap of size k.

Initially, the heap will contain first (k+1) element. We extract the first top element(min elements) from the min-heap which will be our first element of the sorted array. Then the next element will be added into the heap and the second minimum will be extracted. This process will continue till both array and heap is exhausted.

Inserting the element takes O(log k) time, extracting the min element takes O(1) time and heapify the heap after extracting the top element takes
O(log k), where k is the number of elements in the heap. For all the n elements in the array, it takes O(n*log k) time and O(k) space.

Algorithm

  1. Create a min-heap.
  2. Push first (k+1) elements of the array into the heap.
  3. for j : (k+2) to n elements
    • Extract the top element.
    • Add into the output array.
    • Push arr[j] into the heap.
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
 {
	//code
	int i,j;
	int t;
	cin>>t;
	for(i=0;i<t;i++)
    {
        int n,k;
        cin>>n>>k;
        vector<int>v;
        vector<int>out;
        priority_queue<int,vector<int>,greater<int>>pq;
        for(j=0;j<n;j++)
        {
            int a;
            cin>>a;
            v.push_back(a);
        }
        for(j=0;j<k+1 && j<n;j++)
        {
            pq.push(v[j]);
        }
        for(j=k+1;j<n;j++)
        {
            out.push_back(pq.top());
            pq.pop();
            pq.push(v[j]);
        }
        while(pq.size()!=0)
        {
            out.push_back(pq.top());
            pq.pop();
        }
        for(auto f:out)
        {
            cout<<f<<" ";
        }
        cout<<"\n";
    }

	
	return 0;
}

Time Complexity – O(n * log k)
Space Complexity – O(k)