FAQ: Bubble Sort: Conceptual - Algorithm Analysis

Frequently Asked Questions Python FAQ
1

Community%20FAQs%20on%20Codecademy%20Exercises
Community%20FAQs%20on%20Codecademy%20Exercises1000×208 141 KB

This community-built FAQ covers the “Algorithm Analysis” exercise from the lesson “Bubble Sort: Conceptual”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Sorting Algorithms

FAQs on the exercise Algorithm Analysis

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

2

In bubble sort do we consider a comparison as an operation or the actual swapping of elements as an operation? I ask because I read that in the best case scenario bubble sort has O(n) time complexity for an already sorted list. In this case no swaps would be needed but don’t we still do O(n^2) comparisons even if we don’t end up swapping?

1 Like
3

In all sorts, comparison would be a common operation. The difference between methods will result in either less comparisons, and/or less swaps. As time complexity goes, one would gauge that any step in the process is an operation.

Bubble sort makes a gazillion comparisons, and shifts the same value around multiple times. That is, it handles the same objects multiple times. Other methods will generally do this less, or much less.

That doesn’t take away from practicality of bubble sort, though. For short lists it is still very fast. It’s weakness doesn’t betray itself until the data list is large or very large.

I’m not sure the best case is O(n), though. There are n outer iterations, but on each one, there are n-1, n-2, n-3, … comparisons. With no swaps it would be a slam dunk, but probably not that much faster than a completely scrambled list. Worst case would still boil down to O(n^2), as you observe.

3 Likes
4

Yes, the “optimized” version that is given still runs in O(n^2) with a pre-sorted list, although the number of iterations is about 1/2 of those in the “un-optimized” version.

However, if you further optimize it by inserting a flag to tell you when there has been exactly one sweep with no swaps, so as to halt the function, it “sorts” a pre-sorted list in O(n).

Here are iterations for three versions:
The keys are length of a pre-sorted list, the values are iterations of the “un-optimized”, “optimized” and “flagged” versions, respectively. You can see that the first two versions increase x4 for each doubling, while the third doubles for each doubling.

{25: (600,     300,     24), 
50:  (2450,    1225,    49), 
100: (9900,    4950,    99), 
200: (39800,   19900,   199), 
400: (159600,  79800,   399), 
800: (639200,  319600,  799)}

Code Here. Of course, with a random list to sort, the “flag” method tracks the “optimized” method:

{25: (600,    300,    299), 
50:  (2450,   1225,   1219), 
100: (9900,   4950,   4830), 
200: (39800,  19900,  19710), 
400: (159600, 79800,  79722),
800: (639200, 319600, 314347)}
2 Likes
5

Very interesting. So the flag would be preset to one boolean, and the swap would set it to the other. Too cool.

Still, 1/2 is a constant so gets tossed out of Big-O.

3 Likes
6

What does n -1 means and why do we use that most of the time in list?

7

On each pass through the list, one element ends up in its place at the end, or near the end. We shorten the list that gets re-iterated as we go.

8

What is the answer to this question:
What input to bubble sort would produce the worst possible runtime?

9

A reverse sorted list. Now prove me wrong.

10

Oh yes!!! You’re right. :grinning: :grinning: :grinning:

1 Like
11

Don’t discount the effectiveness of this sort method on small sample groups. Many of the more so called ‘efficient’ sort methods don’t show their true value until the sample group is very large. That is where they shine. On small sample groups, though, they are bogged down by their own logic. Bubble sort is faster on 100 items than Quick Sort.

12

So when should we use bubble sort and when not?

1 Like