How to Sort a nearly sorted (or K sorted) array in Java

In this tutorial, we will write the code for this most frequently asked interview question “Sort a nearly k-sorted array” in Java.

Using Min Heap in Java

We are going to use the Java min-heap to do the task. We are going to do this in O(nlogk) complexity. We can use some sorting algorithm to just sort this array and we are done but there is a constraint that we have to do this in less than O(nlogn). Let us see how to approach this. This is one of the common questions of the heap.

We are given that each element is the sorted element at the current position is almost k  distance way. So we just push all the first (k + 1) elements in our min-heap. Then when we will pop the top element of this min-heap, we will get the minimum element at our right position of the sorted array. Then we just insert the next elements one by one and keep doing the previous step and we are done.

This program takes O(nlogk) time complexity. So we get logk instead of logn because of the maximum size of this min-heap is (k+1) which takes O(logk) for insertion.

Let us get to code in JAVA.

import java.util.*; 

public class Main {

    public static void sortK(int arr[], int n, int k) { 
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); 

        for(int i = 0; i < k+1 ; i++){
            pq.add(arr[i]);
        }
        int idx = 0;
        for(int i = k+1 ; i < n ; i++){
            arr[idx++] = pq.peek();
            pq.poll();
            pq.add(arr[i]);
        }
        while(pq.peek() != null){
            arr[idx++] = pq.peek();
            pq.poll();
        }
    } 
    public static void print(int arr[],int n) { 
        for (int i = 0; i < n; i++){
            System.out.printf(arr[i]+" "); 
        }
    } 

    public static void main(String args[]) {

        int[] arr = { 2, 6, 3, 12, 56, 8 }; 
        int n = 6 , k =3;
        sortK(arr, n, k); 
    
        System.out.println( "Sorted array :"); 
        print(arr, n);
    }
}
Output :
Sorted array :
2 3 6 8 12 56

If any doubts then comment below.

Leave a Reply

Your email address will not be published. Required fields are marked *