Another version of bubble sort alernates passes so that the odd passes are like
ID: 674184 • Letter: A
Question
Another version of bubble sort alernates passes so that the odd passes are like the origin , but the even the passes move from the bottom of the array to the top. On the odd passes the larger elements move toward the bottom, uid on the even passes the smaller elements move toward the top. Write this new version of bubble sort. Write a short paragraph that explains exactly why this new version of bubble sort will work. Does this new version of bubble sort change the worst-case analysis? Give an analysis or justification for your? Answer. 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_sort (int a[], int n) {
int i,j, temp, sorted = 1;
for(j=1;sorted && j<=n;j++)
{
sorted=0;
if(i%2==1)
{
for (i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
sorted = 1;
}
}
}
else
{
for (i = n-1; i > 0 ; i--) {
if (a[i] < a[i - 1]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
sorted = 1;
}
}
}
}
}
B)
this will work because we are placing one element each time in its correct position irrespective of whether it is even pass or odd pass
C)
No , new version will not change the worst case analysis of the bubble sort. Analysis follows
in the new version of bubble sort
it will perform n/2 odd ittrations and n/2 even iterations
in each iteration either it is going from top to bottom or bottom to top , which takes n operations
hence total time complexity = (n/2 + n/2) * n = n^2
D)
average case analysis will be as follows
the dominant operation in sorting algorithms is comparision
since we are doing n-1 comparisions in each iteration in every case
on average case also it will perform n-1 operations in each iteration
hence average time complexity for average case = O(n^2)