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.
/** | |
@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++; | |
} | |
} |