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.
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?
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.
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: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.
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
True and then if I have to make a swap, I’ll set it to
already_sorted = False.
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.
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
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.
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.
This really does take a while, doesn’t it? So as you can see, as you increase the size from
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.
Become a Member to join the conversation.