Question

Full and complete answer in order to get credit. Thank you.

Suppose you are given an unsorted list of n distinct numbers. However, the list is close to being sorted in the sense that each number is at most k positions away from its original position in the sorted list. For example, suppose the sorted list is in ascending order, then the smallest element in the original list will lie between position 1 and position k + 1, as position 1 is its position in the original sorted list. Design an efficient algorithm that sorts such a list. The running time of your algorithm should depend on both n and k (a helpful sanity check whether your running time bound makes sense is that, when k is close to n, then the input list is just a generic unsorted list).

Answer 1

We can sort such arrays more efficiently with the help of Heap data structure.
Following is the detailed process that uses Heap.
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time
2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.

Removing an element and adding a new element to min heap will take Logk time.
So overall complexity will be O(k) + O((n-k)*logK)

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

       // adding first (k+1) elements in Heap
       for(int i=0; i<=k && i<arr.length; i++)
           queue.add(arr[i]);

       // Processing others elements
       for(int i = k+1, ti = 0; ti < arr.length; i++, ti++){
           // If there are remaining elements, then place root of heap at target index and add arr[i]
           // to Min Heap
           if(i < arr.length){
               int root = queue.poll();
               arr[ti] = root;
               queue.add(arr[i]);
           }

           // Otherwise place root at its target index and reduce heap size
           else{
               int root = queue.poll();
               arr[ti] = root;
           }
       }
   }

Please let me know in case of any issue