Sorting a K Sorted Array

Problem Statement

In the “Sorting a K Sorted Array” problem we have 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.

Input Format

The first line containing two integer values N and K.

Second-line containing N space-separated integer which is denoting the input array A[].

Output Format

The first and only one line containing N space-separated integers denoting the sorted array.

Constraints

• 1<=N<=10^5
• 1<=K<=10^5
• 1<=A[i]<=10^6

Example

5 2
4 1 5 2 6

1 2 4 5 6

Approach for Sorting a K Sorted Array

We are given an integer array. If the array_A[] is sorted the element at each index will be k distance to the left or to the right. We have to sort the array. We can directly sort the entire array in O(n*logn), but we can use the information given in the question to solve the question more optimally. Let us take an example of an array of size 7, and k=3.

The element at the first index will be among this range [0, 3]. The element at the first index will be the smallest in this range.  For the next index, we have another range. So we have to sort only (k+1) elements for each index. 

So the time complexity of this algorithm will be O(n*logk) which is better than sorting the entire array.

We use a min priority queue of size k+1. After pushing all k+1 items in the priority queue the top element is the smallest in this range. So we put this element at the first index and pop the priority queue. We have to push another element at the k+2nd position. Now the element at the top is placed at the second index and we do a pop operation on the priority queue. Similarly, the process continues until we reach the last index.

Implementation

C++ Program for Sorting a K Sorted Array

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
    cin>>a[i];
    
    priority_queue<int,vector<int>,greater<int>> pq(a,a+k+1);
    int i=0,j=k+1;
    while(j<n){
        a[i++]=pq.top();
        pq.pop();
        pq.push(a[j++]);
    }
    while(!pq.empty()){
        a[i++]=pq.top();
        pq.pop();
    }
    for(auto x:a) cout<<x<<" ";
    cout<<endl;
}

Java Program for Sorting a K Sorted Array

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Iterator;
import java.util.PriorityQueue;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        sort_a_nearly_sorted_array(arr,n,k);
        for(int i=0;i<n;i++){
            System.out.println(arr[i]);
        }
        
  }
  
  public static void sort_a_nearly_sorted_array(int[] arr,int n,int k){

        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        for(int i = 0; i < k + 1; i++){
            pq.add(arr[i]);
        }
 
        int index = 0;
        for(int i = k + 1; i < n; i++) {
            arr[index++] = pq.peek();
            pq.poll();
            pq.add(arr[i]);
        }
 
        Iterator<Integer> itr = pq.iterator();
 
        while(itr.hasNext()) {
            arr[index++] = pq.peek();
            pq.poll();
        }

    }
    
}

7 3
6 5 3 2 8 10 7

2 3 5 6 7 8 10

Complexity Analysis for Sorting a K Sorted Array

Time Complexity

O(N*logK) where N is the size of the given array and K is an integer where each element positions at most k away from its target position.

Space Complexity

O(K) because we use priority_queue and the maximum size of priority_queue is K.