answer in pseudo code The distance of an element Ai in an un

answer in pseudo code

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 ohms (n^2) 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 d_1 denote the the distance of A[i]. Show that A[i] must go through d_i comparisons in any algorithm of this type. Show that any algorithm of this type performs at least Sigma_i d_i/2 comparisons Again suppose a sorting algorithm in each stage swaps only adjacent elements. Show that any such algorithm has running time ohms (n^2) in the worst case. The bad input is always the same. Which is it?

Solution

a) Reverse sorted array will have distance of form: n-1,n-3,n-5...0,2,4...,n-3,n-1

=> Sum of distance -> 2*(n-1+n-3+....0) => omega(n^2)

b) in sorting algorithms each A[i] has to get compared with elements lying b/w i and j (original position) in order to get to j position. (i-j) moves are required to reach j form i position. So distance no of comparison are required.

c) since in part a we have shown complexity would be sum of distance(i). This will become half since comparison required would be only half.

d) is explainable form above analysis.