Member Avatar for 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!

Edited by SebKom because: n/a
  • 3 Contributors
  • 2 Replies
  • 105 Views
  • 14 Hours Discussion Span
  • Latest Post Latest Post by BestJewSinceJC
Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.