[georgiaaaxo]

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?
thanks!

[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.

[georgiaaaxo]

(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
thanks though!

[BabyMaths]

1+2+3+4+5+6+7=28

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

[georgiaaaxo]

(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!!