Full and complete answer in order to get credit. Thank you. Suppose you are give
ID: 3808551 • Letter: F
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).
Explanation / Answer
We can sort such arrays more proficiently with the assist of Heap data structure.
follow is the thorough process so as to use 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, place it in result array, and append a new element to heap from left over elements.
remove an element and totaling a new element to min heap will take Logk time.
So taken as a whole intricacy 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 left over elements, then put 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]);
}
// or else place root at its target index and decrease heap size
else{
int root = queue.poll();
arr[ti] = root;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.