The Student Room Group

quick question about sorting algorithms!

hey!
i'm doing a past paper and not sure how to work out this question:
what is the maximum number of swaps needed to rearrange a list of 8 numbers into ascending order using a bubble sort?
i know that the maximum would be when they are in reverse order, but not sure how i would quickly work out the answer, as they obviously don't want you to work it out.
is there a pattern or something i should know? :s-smilie:
thanks!
Reply 1
It takes n-1 swaps to take the largest/smallest to the end of the list. The second largest is now at the start and you need n-2 swaps to put it in its place. etc..

Maximum number of swaps = 1+2+3+4+.....(n-2)+ (n-1).

....I think.
Reply 2
Original post by BabyMaths
It takes n-1 swaps to take the largest/smallest to the end of the list. The second largest is now at the start and you need n-2 swaps to put it in its place. etc..

Maximum number of swaps = 1+2+3+4+.....(n-2)+ (n-1).

....I think.


oh okay, that makes sense..but still not sure how i would get the answer to the question, which is apparently 28. if there's 8 numbers, using this n-1 thing there would be 7 swaps... i'm guessing you x4 to get 28 but no idea why :s-smilie:
thanks though!
Reply 3
1+2+3+4+5+6+7=28

In general 1+2+3+4+....+(n-2)+(n-1) = n(n-1)/2.
Reply 4
Original post by BabyMaths
1+2+3+4+5+6+7=28

In general 1+2+3+4+....+(n-2)+(n-1) = n(n-1)/2.


ohhhh! got it. thankyou!!

Quick Reply

Latest