Question 12 : (a) The distance of an element A[i] in an unsorted array is |i j|
ID: 674077 • Letter: Q
Question
Question 12:
(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?
Explanation / Answer
a)
Consider A is an unsorted array of integers and B is the sorted array of integers in A.
FindsumofDist(A,B)
{
int sumofDist=0
for( i= 1;i<n;i++)
{
for( j= 1;j<n;j++)
{
if A[i]==B[j]
{
if i>j
sumof Dist=sumofDist+ (i-j)
else
sumof Dist=sumofDist+ (j-i)
}
}
}
}
The above algorithm finds the sum of Distances in ?(n2)
b)
For suppose , an element position in the unsorted array= i.
And the position of the same element in the sorted array= j.
Then the distance of the element di = | i - j | .
Since the algorithm , moves the element one place each time on compression.
Thus, an element is moved to its original place in sorted array after di comparisons only.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.