Pseudocode

Remarks: In all the algorithms, always explain (more precisely try to prove) the correctness of your algorithm

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.

Dont write programs for your solutions . write pseudo code

Question 3: Let A be an unsorted array. Say that all the elements are pairwise disticts, and A[i] is in placeaA[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 or the array is A[1].

The sorted array is < 1, 2, 3, 4, 6, 7 >.

The distance of 7 is 6 1 = 5.

The distance of 4 is 4 2 = 2.

The distance of 3 is 0.

The distance of 4 is 4 2 = 2.

The distance of 6 is 0.

The distance of 1 is 6 1 = 5.