Bubble Sort (Number of Steps)

[SebKom]

Hello coders, newbie on board!

Just a quick question: How do I calculate the number of steps a bubble sort takes to sort a database of n entries?

On my notes it is written that "It is easy to see that a bubble sort of n records requires n−1 comparisons on the first pass, n−2 on the second and so on down for a total of n−1 passes" but I don't really understand it. Neither the conclusion itself, nor how the guy came to that conclusion.

I'd appreciate it if you could explain me the mathematics behind it, I don't want the answer, I want the way to the answer. :)

Thanks in advance!

[Rashakil Fol]

That's just saying it takes n-1 comparisons on the first pass, n-2 on the second, n-3 on the third, ... and 1 on the n-1'th pass -- so there are a total of n-1 passes.

So, ask yourself: why? What does bubble sort look like? What does it do, during each pass? Why is it not n-1 comparisons on every pass? Look at the actual algorithm's implementation.

As for the total number of comparisons: you'll want to add up the number of comparisons on each pass. What is 1 + 2 + 3 + ... + (n-2) + (n-1)? Hmmm, a math problem.

[BestJewSinceJC]

http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%C2%B7_%C2%B7_%C2%B7