Question $3$: Let A be an unsorted array. Say that all the elements are pairwise districts,

and A$[$i$]$ is in place A$[$ji

$]$ in the sorted array. We define the distance from the correct

place of A$[$i$]$ as $|$i $$ ji

$|.$ Say that all the distances of every A$[$i$]$ is at most $20.$ Give an

approximation algorithm for sorting under this assumption.

Example: Let A $=<7,4,3,2,6,1>.$ Say that the first entry of the array is A$[1].$ The

sorted array is $<1,2,3,4,6,7>.$ The distance of $7$ is $61=5.$ The distance of $4$ is

$42=2.$ The distance of $3$ is $0.$ The distance of $4$ is $42=2.$ The distance of $6$ is

$0.$ The distance of $1$ is $61=5.$ Remarks: In all the algorithms, always explain precisely your solution or prove if required.

You Always Must analyze the running time of any algorithm. The time complexity should

be as small as possible. A correct algorithm with large complexity, may not get full credit.

Don$$t write programs for your solutions.