You are given an integer b and an almost sorted array A[1..n] of distinct integers, where...

 

Transcribed Image Text:

You are given an integer b and an almost sorted array A[1..n] of distinct integers, where each element can be misplaced by at most b positions. (i.e. the sorted position of the i-th element A[i] is at least i-b and at most i+b.) You are asked to design an algorithm to sort the array A. You need to optimize your running time and extra space. Analyze the running time and the extra space in terms of n and b. [Hint: Modify selection sort? Use a heap?] You are given an integer b and an almost sorted array A[1..n] of distinct integers, where each element can be misplaced by at most b positions. (i.e. the sorted position of the i-th element A[i] is at least i-b and at most i+b.) You are asked to design an algorithm to sort the array A. You need to optimize your running time and extra space. Analyze the running time and the extra space in terms of n and b. [Hint: Modify selection sort? Use a heap?]