Sort A K Sorted Array

We look at how we can sort an almost sorted array, or a "k sorted array". We take advantage of the fact that the array is already partially sorted and use a heap based approach to deduce who can be where in the final sorted output.

Table of Contents

Code Sample

/**
@author Benyam Ephrem
Sort A Nearly Sorted Array: https://www.geeksforgeeks.org/nearly-sorted-algorithm/
I haven't written automated tests for this code so no guarantees. But it has been
manually tested thoroughly.
The video to explain this code: https://www.youtube.com/watch?v=yQ84lk-EXTQ
*/
public void sortNearlySortedArray(int[] arr, int k) {
/*
Create a min heap. Without a comparator Java (as of Java 10) defaults putting
the smallest items at the front of the priority queue.
Not sure if the Java PriorityQueue is implemented underneath with a binary heap...
but yeah. Remember that a heap is an implementation of the priority queue ADT
(abstract data type)
*/
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int n = arr.length;
/*
Add the first k elements to the min heap. Guard against the case that
there are less than k items in the whole array
*/
for (int i = 0; i < k && i < n; i++) {
minHeap.add(arr[i]);
}
/*
Add and place...add and place...add and place from the heap. Initially, we
added items from index 0 to index k - 1. We continue reading from index k
and begin our minimum element placements at index 0.
Continue while the read index stays within the index bounds of the array.
When it runs over we will have no more items to add to the heap for consideration.
*/
int readIndex = k;
int placementIndex = 0;
while (readIndex < n) {
/*
Add the next element to be considered in the heap. The heap will
hold at max k + 1 items.
*/
minHeap.add(arr[readIndex]);
readIndex++;
/*
Remove the smallest item to place into the array. This item will be
placed where it belongs by the definition of what k represents.
*/
arr[placementIndex] = minHeap.poll();
placementIndex++;
}
/*
Empty out the rest of the heap & do placements.
*/
while (!minHeap.isEmpty()) {
arr[placementIndex] = minHeap.poll();
placementIndex++;
}
}
view raw SortAnAlmostSortedArray.java hosted with ❤ by GitHub