Full and complete answer in order to get credit. Thank you. Suppose you are give
ID: 3804841 • 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
for i = 1 to n //loop iterates n times
minPos = findMinPosition(i, min(i+k,n)) //complexity of O(k) since searches max k elements
swap (a, i, minPos) //Swap element at ith position with minimum element of the array 'a'
a[i] = minElement;
//end of for i loop
The above algorithm is self-explanatory, still am explaining it once again
Step 1: iterate i for each element of the array (i = 1 to n)
Step 2: search for the minimum element within the range of k (search from i to i+k, if i+k is more than n, search upto n)
Step 3: Swap/insert the smallest element at the ith position. (Shift the required elements right or simply swap smallest element with ith element)
Complexity = O(nk)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.