0

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!

Edited by SebKom: n/a

3
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by BestJewSinceJC
0

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.