Sort a Nearly Sorted Array(K Sorted Array)

In this article, we will discuss sorting a nearly sorted or K sorted array using Heap data structure in Java.

Given a K sorted array means any given element of the array is at most K distance away from its actual position. For example, in a given array [10, 9, 8, 7, 5, 70, 60, 50] the element 5 is 4 index distant from its actual position. Here, K is 4. The value of K can be on any side either K index left or K index right but not more than that.

Similarly, in the array [3, 2, 1, 9, 8] the value of K is 2 as the element 1 is at a distance of 2 from its actual position.

Other Sorting Techniques

There are multiple sorting techniques that can be applied to sort any given array. We can prefer quick sort to sort any given array with the best time complexity of O(nlogn) or merge sort with worst-case complexity of O(nlogn).

But as per the given problem, the array is already K sorted or nearly sorted, and hence for the optimal solution we should be able to sort it within O(nlogk) time complexity. Now, this time complexity of O(nlogk) can be achieved with Heap sort.

Heap Sort

Heapsort is an in-place algorithm and a special case of a balanced binary tree data structure. A heap can be a max heap or min-heap. We have already discussed the Heap sort techniques in my last article to find the Kth largest and smallest element.

With heap sort we don't have to unnecessarily sort (n - k) elements to sort K sorted array in comparison to merge sort.

Sorting with Heap Sort

To sort this k sorted array, first, we will insert K elements of the given array in the min-heap. Hence, after every K element insertion i.e K+1, the smallest element will be at the top as the smallest element automatically bubbles at the top in case of min-heap. Then, we can poll the element from the Heap and insert it into the given array.

The time complexity would be O(k) + O((n-k)*logk) = nlogk

Below is the implementation of the algorithm in Java.

import java.util.Arrays;
import java.util.PriorityQueue;

public class KSorted {

    public static void sortKSortedArray(int[] array, int k){
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int length = array.length;
        for (int i = 0; i < k; i++){
            minHeap.add(array[i]);
        }

        int index = 0;
        for (int i = k; i < length; i++){
            minHeap.add(array[i]);
            array[index] = minHeap.poll();
            ++index;
        }

        while(minHeap.iterator().hasNext()){
            array[index] = minHeap.poll();
            ++index;
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 5, 70, 60, 50};
        System.out.println(Arrays.toString(arr));
        KSorted.sortKSortedArray(arr, 4);
        System.out.println(Arrays.toString(arr));
    }
}

[10, 9, 8, 7, 5, 70, 60, 50]
[5, 7, 8, 9, 10, 50, 60, 70]

Conclusion

In this article, we will discuss sorting a nearly sorted or K sorted array using Heap data structure in Java.