The Student Room Group

D1 HELP

My textbook says that the maximum no. of comparisons for bubble sort is 0.5n(n-1). Is this only true if the list is in reverse? For example you has sort the list (1,2,3,4,5,6,7,8,9,10) form largest to smallest would it take 0.5*10*9=45 comparisons.

For example, the answer to question 1(iii) is 5+4+3+2+1=15 (https://drive.google.com/file/d/0B6vHHB9DM_MhazNFSzR3anBXSTg/view)

How are we meant to know how many comparisons there are in each pass. Also, wouldn't the answer only be 15 if the list was in reverse?

Thanks
Reply 1
bump
Reply 2
You find the comparisons by listing the comparisons for each pass when you are sorting. Theres no easy way. I think the max number of comparisons
0.5(n)(n-1) is the formula for total passes not one passes and it asks for total number of comparisons. Not 100% sure tho.
(edited 7 years ago)
Original post by SWISH99
My textbook says that the maximum no. of comparisons for bubble sort is 0.5n(n-1). Is this only true if the list is in reverse? For example you has sort the list (1,2,3,4,5,6,7,8,9,10) form largest to smallest would it take 0.5*10*9=45 comparisons.

For example, the answer to question 1(iii) is 5+4+3+2+1=15 (https://drive.google.com/file/d/0B6vHHB9DM_MhazNFSzR3anBXSTg/view)

How are we meant to know how many comparisons there are in each pass. Also, wouldn't the answer only be 15 if the list was in reverse?

Thanks

Comparisons is n-1 per pass. You do a comparison for each pair next to each other and you look at every one per pass so it's the total numbers in that pass -1.
Original post by fpmaniac
You find the comparisons by listing the comparisons for each pass when you are sorting. Theres no easy way. I think the max number of comparisons
0.5(n)(n-1) is the formula for one pass not all passes and it asks for total number of swaps. Not 100% sure tho.

No thats total comparisons. For each pass its n-1 (n is remaining numbers).
Reply 5
Original post by Vikingninja
No thats total comparisons. For each pass its n-1 (n is remaining numbers).


Oops, Wrote it the other way round. Also wrote swaps instead of comparisons lol.
Original post by fpmaniac
Oops, Wrote it the other way round. Also wrote swaps instead of comparisons lol.


Ive forgotten how to derive the equation since I've only ever seen it once which was a show that question but the 0.5n gives the average comparisons per pass and n-1 is the number of passes.
Reply 7
Original post by Vikingninja
Comparisons is n-1 per pass. You do a comparison for each pair next to each other and you look at every one per pass so it's the total numbers in that pass -1.


so its n-1 per pass in every situation?
Original post by SWISH99
so its n-1 per pass in every situation?


Yes where n is what is remaining. Though a well sorted listed at the start before doing bubble sort can terminate early in terms of passes.

Also your equation for max comparisons is when its completely in reverse.
Reply 9
Original post by Vikingninja
Yes where n is what is remaining. Though a well sorted listed at the start before doing bubble sort can terminate early in terms of passes.

Also your equation for max comparisons is when its completely in reverse.


thanks,
but why does the equation still apply for the example i posted even though the list is not in reverse?
Original post by SWISH99
thanks,
but why does the equation still apply for the example i posted even though the list is not in reverse?


Looked at the thing again. It's because of that 4 on the right hand side, it needs to be taken from the far right to the far left so max number of passes are needed so max number of comparisons.

Quick Reply

Latest