I am working on some practice problems regarding bubble sort. I have to find the
ID: 3789555 • Letter: I
Question
I am working on some practice problems regarding bubble sort. I have to find the number of swaps in the best, worst, and average case. The pseudocode for bubble sort is..
for i = n downto 2 do
for j = 1 to i-1 do
if A[j] > A[j+1]
then A[j] A[j+1]
end if
end for
end for
This the questions:
Assume the we are sorting an array with even number of elements. Assume that the first and second smallest elements are next to each other (somewhere
in the input), the third and fourth smallest elements are next to each other, the fifth and sixth smallest elements are next to each other, etc.
For example, assume n = 10, the input might look like
50, 60, 40, 30, 90, 100, 10, 20, 80, 70
(a) Assume each of the above pairs are out of order (so that the second smallest element comes
before the smallest, the fourth smallest element comes before the third smallest, etc.). For example,
60, 50, 40, 30, 100, 90, 20, 10, 80, 70
What is the exact number of exchanges in the best case?
(b) Assume each of the above pairs are in order (so that the smallest element comes before the second smallest, the third smallest element comes before the fourth smallest, etc.). For example,
50, 60, 30, 40, 90, 100, 10, 20, 70, 80
What is the exact number of exchanges in the worst case?
(c) Assume each of the above pairs are in a random order.
What is the exact number of exchanges in the average case?
For the best case, I listed the items in this order.
20, 10, 40, 30, 60, 50, 80, 70, 100, 90.
After running the bubble sort, I got 5 exchanges. I not sure how to turn that into a function of n. I need to solve this using summation but I am not quite sure how to do it.
For the worst case, I know that pairs will be in reverse order. But I am not sure how to turn that in to summation to find the exact number of exchanges(swaps).
And I am totally lost on how to do the average case.
I would really appreciate if someone can show me how to figure out the number of exchanges for all three cases.
Explanation / Answer
The bubble short will give either assending order or dissending order of the given numbers by using swaping while compare with besides value (either assending or dissending)
now , in this case , the given pseudocode is saying that , trying to keep the entered values in assending order.
the swaping will happened when ever before value is grater than the next value, in the same way it will check till the last value ,
nothing but as per your example the flow will be as below
50, 60, 40, 30, 90, 100, 10, 20, 80, 70
First out loop will check as like this , total 10 values so 9 times second loop will execute to check for swapping
50-60 40 30 90 100 10 20 80 70 (1st comparision) will not swap
50 60-40 30 90 100 10 20 80 70 (2nd comparision) will swap
50 40 60-30 90 100 10 20 80 70 (3rd comparision) will swap
50 40 30 60-90 100 10 20 80 70 (4th comparision) will not swap
50 40 30 60 90-100 10 20 80 70 (5th comparision) will not swap
50 40 30 60 90 100-10 20 80 70 (6th comparision) will swap
50 40 30 60 90 10 100-20 80 70 (7th comparision) will swap
50 40 30 60 90 10 20 100-80 70 (8th comparision) will swap
50 40 30 60 90 10 20 80 100-70 (9th comparision) will swap
reslt of first outer loop will be
50 40 60 30 90 10 20 80 70 100
This first step we will get highest value (100) at the last position by swapping 6 times .
in the same way 90, 80, 70 , 60 , 50 , 40, 30 , 20, 10 positions will get set by swapping when it needed
And we cant decide the number of swapping for bubble short always in function of n by seaing the input
a)
as per information , we can cosider that best case is nothing but less swapping of values
So,as per the given example
60, 50, 40, 30, 100, 90, 20, 10, 80, 70 , we cant decide the best case , because still there will be swapping cases for this .
So, my solution for the best case , if the input will be the same order for the required output order.
it means ,the above pseudocode is saying that , trying to keep the entered values in assending order.
So, if we give the input in assending order then bubble short will set the assending order with out swapping the values .
Example is --> Input is 10,20,30,40,50,60,70,80,90,100 (for this case , swapping will not occur to keep them in assending order
output is 10,20,30,40,50,60,70,80,90,100
b)
as per information , we can cosider that , worst case is nothing but less swapping of values
So,as per the given example
50, 60, 30, 40, 90, 100, 10, 20, 70, 80. we cant decide the worst case , because still this will not give maximum swapping cases .
So, my solution for the worst case is, if the input will be opposite order for the required output order.
it means ,the above pseudocode is saying that , trying to keep the entered values in assending order.
So, if we give the input in desending order then bubble short will set the assending order with maximum swapping values.
Example is --> Input is 100,90,80,70,60,50,40,30,20,10 (for this case , swapping will not occur to keep them in assending order and output is 10,20,30,40,50,60,70,80,90,100.
c)
The given a) and b) examples will comes under average case bceause the swappings will not be minimum and also will not be maximum
and to find swapping count for the avarage case , we need to increas the count variable in swapping logic then we will know at the end how many swappings done for the average case
and also for worst and best case as well. please find the pseudocode for said point
int a=0;
for i = n downto 2 do
for j = 1 to i-1 do
if A[j] > A[j+1]
then A[j] A[j+1]
a++; //will be the total number of swapping count for given input
end if
end for
end for
For best case ,we can say that "n-n" swapping count
value for best case is "0" (10-10 = 0) for given input 10,20,30,40,50,60,70,80,90,100
For worst case , we can saying that "(n(n-1))/2".
value for worst case is 45 ((10(9))/2 = 45) for given input 100,90,80,70,60,50,40,30,20,10.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.