Bubble Sort
Here are resources for more information about Python decorators:
00:00 Let’s talk about a really basic sorting algorithm, bubble sort. Bubble sort is well known because it’s really basic to implement, and it’s a really basic algorithm to think about. But it is quite slow, and so it’s not something that’s normally used in practice other than as a quick sorting algorithm that you can write if you really need one if you don’t have a sorting algorithm already in your standard library.
00:26 The basic idea of bubble sort is probably what you would think of if someone asked you to sort a list without ever having done any sorting algorithm work before. The basic idea is to move the largest item of the list to the end, then the second largest to the second-to-last position in the list, then the third largest, and so on until the whole list is sorted.
00:46 Now bubble sort specifically is named because the element in question bubbles to the top of the list in a series of swaps with adjacent elements. So looking at this diagram over here on the right, you’re going to start at the beginning and you’re going to say 8 is more than 2, so I need to swap 8 and 2 because 8 is greater, so it needs to be farther in the list. Of course, this is assuming that we’re sorting in ascending order.
01:10 You could define a comparator to sort in descending order if you wanted to but just for the moment let’s assume we’re sorting in ascending order. So, you swap 8 and 2. Then you move up and 8 is still greater than 6, so you swap it again. It’s greater than 4, you swap it again.
01:26 It’s greater than 5, you swap it again. And, finally, 8 is at the end of the list. There’s nothing left to swap it with, so you know that the last element in the list is the greatest element in the list. Now you’re going to start here again, and 2 and 6 don’t need to be swapped, so you move up to 6.
01:41 Now 6 and 4 can be swapped and 6 and 5 can be swapped, and then you would actually move to this 5 and you would see that it is in the correct order, you’d see that this is in the correct order, and so you’re actually done with those elements.
01:55 So that’s the basic idea of bubble sort is just keep swapping until the biggest element’s at the end and then you kind of stop considering the last element because we know that’s in the right place and you just continue on smaller and smaller sections of this list until the whole thing is sorted.
02:12 Let’s take a look at how this manifests itself in code.
02:16
Okay, let’s do some bubble sorting! I’m going to define a bubble_sort() function. It’s going to take in a list or a collection of items. And if you remember from the slide I showed you a second ago, you’re going to go through the entire list, right?
02:31
So, moving the largest item to the end of the list, and then the second largest item to the second-last position in the list, and so on. Right? So that implies that you’re going to need to loop through all of the items in the list, so for i in range(len(items)), right?
02:46 So, this is the indices of each item in the list. And then at each point during that iteration, you’re going to need to go through and bubble that biggest item all the way up to the end of the list.
02:58 So that implies another list, and the range for that list doesn’t need to be the whole list. It just needs to be all of the items you haven’t looked at yet.
03:07
So, that’s len(items) - i, right? Because i is the number of items that I’ve actually already considered. And one little thing here is that you actually need to subtract 1 from that because since we’re going to be swapping, you don’t want to try to swap the last element because once you’re at the last element, you don’t need to do any more.
03:27 So you need to go one less than the length of the list minus the number of items already considered, right? So, let’s go through. And then what do you actually need to do here? You need to do some swapping, right?
03:38
You need to check if the item that you’re at—so if items at j, if this is greater than items at j + 1 you know that they’re in the wrong order, so they need to be swapped, right?
03:53
So I’ll say items at j, items at j + 1—
03:59 the two of these items are going to swap spots. So I’m just going to copy-paste here because of Python’s awesome… Whoops, I’ll actually copy and paste. But because of Python’s awesome multiple assignment feature, so I can just go here and I can swap these two indices and now these two items will swap places.
04:19 And then that should really be all that I actually need here, right? Because what you’re going to do is you’re just going to go up and you keep swapping and this swapping will ensure that the biggest item is always moving up throughout the list. And if that’s not entirely clear, I would encourage you to write down a list and to do this algorithm on paper, on your own, just so that you can get a clearer sense of how this swapping procedure actually works. Now there’s one thing that I want to mention here, which is that this could do some extra work.
04:49 So, imagine the case where the list is already sorted, right? You could go through here and you could never have to swap an item, but you’re still going to be doing all of this extra iteration even if the very first time through the list you see that it’s already sorted.
05:03
So what I’m going to do is I’m going to say here for i in range(len(items)): I’m going to first set a parameter called already_sorted to True and then if I have to make a swap, I’ll set it to False, already_sorted = False.
05:19
Because that means since I had to swap something, I know it can’t already have been sorted. But then what I can do here is I can say if already_sorted, so if I didn’t have to swap anything in my whole run through the list, then I can just break. That will save a little bit of work here.
05:35
So, let’s see it run. The first thing I’m going to do is I’m just going to define a list of items, and it can just be anything, so let’s say [1, 2, 5, 3, 2, 3, 8, 1], just for fun.
05:49
And then I’ll just print out here bubble_sort(items).
05:55
So, this is pretty darn cool and I can just run it in the terminal. I can say python bubble_sort.py, and as you can see, it gives me a nice sorted list here of these non-sorted elements.
06:05
So, that’s pretty cool! It seems to work out just fine in this case. Now I mentioned that bubble sort is a pretty slow-sorting algorithm. And that’s definitely true, and the reason for that is these two nested loops, both of which can cover at the worst case the whole length of the items—or, one less than the whole length of the items, right?
06:23 So whenever you have two nested loops, both of which are going through a list, you can normally assume that that is an order of n squared algorithm.
06:32
In fact, that’s exactly what it is. So let me show you a little bit of timing information. I have a timing module, so I’m going to say from timing import timed_func.
06:41 Uh, not runction, function. And then I can use this decorator, and I’ll add in some resources to show you how to do this on your own if you want, but just know that this is going to time this function whenever it runs.
06:54 Actually, while I’m on the subject, here is the decorator function that I’m using. And if you’re not familiar with decorators, I encourage you to check out Real Python has an awesome video course and an article on decorators—in fact, several articles, and they’re all awesome.
07:09 So check that out if you want more info on how this works. But essentially what it does, it just takes in a function, starts a timer, then runs the function, and then prints out the end time minus the start time, which gives you approximately the runtime of the function. Back to bubble sort.
07:27
And now let me do a little bit of modification here. I’m going to say items = … Let’s import random,
07:35
and I can say items = [random.randint()], let’s give it up to 1000 or something, for _ in range(1000).
07:46
so let’s see how long it takes to sort a list of random integers, a list of length 1000 of random integers somewhere from 0 to 1000.
07:56
And I almost forgot, random.randint() actually takes a start as well as a stop parameter, so there that is. Now let’s try to run this and see how long it takes.
08:06 And I forgot that this is going to actually print out the whole list.
08:14
So on a list of a thousand elements, this took about a tenth of a second, which is pretty cool. And I can up this maybe to 10000 elements just for fun, and that takes a substantial amount of time longer. As you can see, it’s still going, just as I’ve been talking this whole time. Wow.
08:31
This really does take a while, doesn’t it? So as you can see, as you increase the size from 1000 to 10000 elements, bubble sort takes a ridiculous amount of time longer. I mean, it took 13 and a half seconds as opposed to a tenth of a second.
08:46 So as you can see, this does not really scale well as the size of your list increases. So, let’s move on to the next Python sorting algorithm that I want to show you, which is insertion sort.
Bartosz Zaczyński RP Team on May 31, 2021
@Manu Both functions use an adaptive sorting algorihm called Timsort, which was named after Tim Peters who was a major contributor to Python.
dev782 on March 18, 2022
from timing import timed_func
How to fix this error?
cannot import name 'timed_func'
rynesmith on July 2, 2022
As an alternative to creating the decorator, you can also code in a start time and finish time. Finding the difference will reveal the total time elapsed for the function.
Below I imported the standard library’s time module and used its perf_counter function to mark the start and finish times.
import time
import random
def bubble_sort(items):
for i in range(len(items)):
already_sorted = True
# You minus the 1 since the number items[i] is compared with each of the others. It isn't compared to itself.
for j in range(len(items) - i - 1):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
already_sorted = False
if already_sorted:
break
return items
items = [random.randint(1, 1000) for _ in range(1000)]
start_time = time.perf_counter()
print(bubble_sort(items)[1])
finish_time = time.perf_counter()
print(finish_time - start_time)
aquibmir on Feb. 25, 2024
I don’t see how the already_sorted flag reduces time. The program still has to run the nested loop to figure out if it’s sorted or not.
And when using @timed_func, it seems the execution time is added as the second element of the list, hence it has to be printed out with print(bubble_sort(items)[1]) . Correct?
Bartosz Zaczyński RP Team on Feb. 27, 2024
@aquibmir With the already_sorted flag, you stop the outer loop as soon as the inner loop determines that the elements are sorted. Consider a list of numbers that are already in the expected order:
bubble_sort([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
In that case, you’ll loop over all elements exactly once, concluding there’s no need to sort them anymore because you haven’t swapped any of the element pairs during the iteration. Otherwise, if you didn’t have that flag, then the outer loop would run ten times for all ten elements in your sequence of items.
Become a Member to join the conversation.
Manu on May 31, 2021
Which algorithm runs when we call
sort()&sorted()methods?