Remarks: In all algorithm, always explain how and why they work. ALWAYS, analyze the complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. In all data structures, try to minimize as much as possible the running time of any operation.

1. Question 1: (a) The distance of an element A[i] in an unsorted array is |i j| with j the place of A[i] in the sorted array. For example, in the array 6, 4, 2, 3, 8 the distance of 8 is 0 (8 is in its proper place), the distance of 6 is 3 (6 is now first in the order but should be forth), the distance of 4 is 1, the distance of 2 is 2 and the distance of 3 is 2. Show an input where the sum of distances is (n 2 )

(b) Suppose a sorting algorithm in each stage swaps only adjacent elements. That is, (like for example Bubble-Sort and Simple Insertion-Sort) in each stage it swaps A[i] and A[i + 1] for some i. Let di denote the the distance of A[i]. Show that A[i] must go through di comparisons in any algorithm of this type.

(c) Show that any algorithm of this type performs at least P i di/2 comparisons

(d) Again suppose a sorting algorithm in each stage swaps only adjacent elements. Show that any such algorithm has running time (n 2 ) in the worst case. The bad input is always the same. Which is it?