A different version of bubble sort keeps track of to lowest posotion in the arra
ID: 3600178 • Letter: A
Question
A different version of bubble sort keeps track of to lowest posotion in the array where a swap occured occurred, and on the next pass it starts one below this position.
a. Write this new version of bubble sort.
b. Write a short paragraph that explains exactly why this new version of bubble sort will work.
c. Does this new version of bubble sort change the worst-case analysis? Give an analysis or justification for your answer.
d. This new version of bubble sort does change the average-case analysis. Give a detailed explanation of what is involved in calculating this new average-case analysis.
Explanation / Answer
a.
void bubble(int a[], int n){
for(int i=0; i<n; i++){
int swaps=0;
for(int j=0; j<n-i-1; j++){
if(a[j]>a[j+1]){
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
swaps++;
}
}
if(swaps==0)
break;
}
}
b. Newer Version of bubble sort is an enhancement to the bubble sort algorithm. It won’t improve the algorithm worst case running time but on an average case or for nearly sorted array it is a great improvement and it will work as it skips many passes by using a flag that is set if an exchange is made after an entire pass over the array. If no exchange is made, then it is clear that the array is already in order as no two elements need to be switched.
New Best case = O(n)
c. This algorithm does not improve the worst case running time. The worst case scenario of bubble sort occurs when array is reverse sorted which is O(n*n) in both the cases and before to sort the array we have to iterate over the whole array n*n times which remains same in modified bubble sort also as the array is reveresed sorted so swaping will occur upto the last element which is n*n times.
d.
Recall that a pair (A[i],A[j])(A[i],A[j]) (resp. (i,j)(i,j)) is inverted if i<ji<j and A[i]>A[j]A[i]>A[j].
Assuming your algorithm performs one swap for each inversion, the running time of your algorithm will depend on the number of inversions.
Calculating the expected number of inversions in a uniform random permutation is easy:
Let PP be a permutation, and let R(P)R(P) be the reverse of PP. For example, if P=2,1,3,4P=2,1,3,4 then R(P)=4,3,1,2R(P)=4,3,1,2.
For each pair of indices (i,j)(i,j) there is an inversion in exactly one of either PP or R(P)R(P).
Since the total number of pairs is n(n1)/2n(n1)/2, and the total number and each pair is inverted in exactly half of the permutations, assuming all permutations are equally likely, the expected number of inversions is:
n(n1)/4 = O(n*n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.