Description

We are super bubbly about bubble sort! We dig into our second sorting algorithm and break down how it works and why it's actually not a great way of sorting things.

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Bubbling Up With Bubble Sorts from her basecs blog series.

Transcript

[00:00:00] SY: Okay. I’ve got a very exciting announcement. We finally have a date for Codeland, our annual conference. It’s happening July 22nd in New York City. Early bird tickets are now on sale. For just 99 bucks, you get breakfast, lunch, dinner, a coding workshop, technical talks and after-party, and of course an amazing community. Sale ends March 10th. Go to codelandconf.com for more info. Link is in your show notes.

[00:00:30] (Music) Welcome to the Base.cs Podcast where we explore the basics of computer science concepts. I’m your host Saron, founder of CodeNewbie.

[00:00:37] VJ: And I’m Vaidehi Joshi, Author and Developer.

[00:00:40] SY: And she is the brilliant mind behind the Base.cs Blog Series. Today we’re talking about.

[00:00:44] VJ: Bubble Sort. Well, you know, I wanted to do a drum roll.

[00:00:53] SY: This season of the Base.cs Podcast is brought to you by our wonderful friends at DigitalOcean. DigitalOcean provides the easiest cloud platform to deploy, manage, and scale applications of any size. They remove infrastructure friction and provide predictability so you can spend more time building what you love. Try DigitalOcean for free by going to DO.co/codenewbie and get $100 in infrastructure credit. Link is in your show notes.

[00:01:22] This season is also brought to you by the fine folks at Linode. If you’ve got a personal project, a small business or a big business with lots of data, Linode offers you secure hosting for all your infrastructure needs. They are a Linux cloud hosting provider where you can get a new server up and running in under a minute. Plans start at one gigabytes of RAM for just five bucks a month. And with the promo code CodeNewbie2019, you can get a $20 credit. So go to linode.com/codenewbie and give it a try. Also, they’re hiring. Check out their jobs at linode.com/careers. Link is in your show notes.

[00:01:59] SY: Okay, let’s get started. Okay. What is bubble sort? I know it’s an algorithm because we’re talking about algorithms. What is this algorithm about? How does it work?

[00:02:11] VJ: So bubble sort is also a sorting algorithm. We can give it a little bit more context there. It is a sorting algorithm that iterates through a collection or a list that’s unsorted and it compares every pair of adjacent elements in the list and compares them based on their size.

[00:02:31] SY: Okay.

[00:02:31] VJ: So it’s comparing two elements at a time and it’s basically looking at them and checking if they’re in the right order, and if they’re not in the right order, it swaps them and it just continues to swap elements in pairs until the whole collection is sorted.

[00:02:47] SY: So that sounds like something I would do. I don’t know. It sounds easy. It sounds like straightforward and bubble sort to me as always had this kind of scary image of like, “Bubble sort!” It’s always like seems scary to me, but this seems like pretty straightforward but to make sure, can we like walk through an example to make sure I think this is doing what I think it is doing?

[00:03:05] VJ: Yeah. Let’s do it.

[00:03:06] SY: So let’s do an example. Let’s take a list of numbers, 9, 7, 4, 1. They are intentionally backwards in their sortingness in their organization. So 9, 7, 4, 1. Okay. So if I am a bubble sort algorithm, you said that we’re going to iterate through the list, which I assume means we’ll start at the first one.

[00:03:29] VJ: Yup.

[00:03:29] SY: Okay. So we have 9.

[00:03:31] VJ: Yup.

[00:03:32] SY: Okay. And then it says compare each pair of adjacent elements, so 9 and whatever is next to it which is a 7.

[00:03:40] VJ: Yup. Totally.

[00:03:41] SY: Okay.

[00:03:41] VJ: What you’re doing is you’re starting with the first element and you’re just comparing it to the next one. So in this case 9 and 7.

[00:03:47] SY: Okay.

[00:03:48] VJ: Because we’re comparing like we can literally think of comparison operators like greater than, less than, whatever, and use that to look at the two elements and see if they are in order since we know we’re trying to go from probably smallest to largest in ascending order.

[00:04:03] SY: Right. So I’m comparing my 9 and my 7 and I’m like, “This is wrong, 9 needs to be after 7.” So now what do I do?

[00:04:12] VJ: So now you know that the elements are out of order and all you know are the two items in this pair, 9 and 7. So you know that one is larger. So you just need to swap them so that they’re in the correct order.

[00:04:23] SY: Okay.

[00:04:23] VJ: So in this case, you would swap 7 to come before 9 and 9 to come after 7. So you would move 9 to 7’s position and swap 7 into 9’s position.

[00:04:32] SY: Okay. So now my new list at this point in time is now 7, 9, 4, 1. Okay. So then if we look back at our algorithm again, it says that I’m going to compare, well, and like 9 isn’t in its right place yet. If we’re going to put an order, we kind of need to be like all the way at the back, right? We need to put at the end of the list.

[00:04:52] VJ: Yup. And what you’re basically doing is you’re kind of going to follow along with this first element until it’s in its right spot.

[00:05:00] SY: Okay. So I’m going to stick with 9.

[00:05:01] VJ: Yeah, it’s like your first run of this algorithm. Well, it’s the first run of the algorithm and so you’re kind of like, “This run, I’m friends with 9 and I’m going to take 9 all the way to its nice little spot where ever has to live.”

[00:05:14] SY: Oh my God, I love that. Yes. Okay. Okay, I’m excited now. Okay. So I’m friends with 9.

[00:05:23] VJ: I’m friends with 14.

[00:05:27] SY: Why is yours bigger than mine? Okay. So I’m friends with 9. So I started by saying, “Hey, 9 we’re buddies. I’m going to put you in your position so you’re nice and comfy and we’re going to start by comparing you to your neighbor, which is 7. You are not in the right place so I’m going to swap you with 7.” And now we do the thing. We’re not done with our run because we’re still with 9, but we did a thing, right? Okay. Now my new order currently is 7, 9, 4, 1, but now I have to compare my friend 9 to the next thing, which is 4.

[00:06:02] VJ: Yup. You got it.

[00:06:03] SY: Okay. So now I go 9 and 4, which one is bigger, 9 is bigger. Okay, 9, you’re still not in the right place. Now I’m going to swap you.

[00:06:11] VJ: Exactly. And when you’re swapping you’re not really thinking that much or at all about the elements you already looked at.

[00:06:17] SY: I don’t really care about those.

[00:06:18] VJ: Yeah.

[00:06:19] SY: Because I’m not friends with them. They can’t stay with us.

[00:06:25] VJ: So you’re going to swap 9 and 4, but the minute you do that and like you’ve moved on you’ve compared the first and the second element and now you’re comparing the second and the third element and then you’re going to go on from second and third to third and fourth and you kind of aren’t really thinking about whether 7 and 4 are in the right position because spoiler alert, they’re not, but that’s okay. We’re not going to worry about it now.

[00:06:46] SY: Right. Okay. So after my latest swap, my new order is 7, 4, 9, 1. I’m still with my 9, I’m still with my best friend 9, and I’m like, “Okay, there’s one more neighbor that we need to talk to.” So we’re going to compare my 9 with my 1. Is 9 bigger than 1? Yes, it is. We’re going to do our last swap.

[00:07:06] VJ: Yup.

[00:07:07] SY: And now my 9 is at the end and I guess I can like look for a neighbor. I can say, “Is there anyone else here?” “I don’t know. No, there isn’t.” “Okay. Cool.”

[00:07:17] VJ: Is there anyone out there? I’m at the edge of a cliff.

[00:07:24] SY: Tell me now. Yes.

[00:07:26] VJ: I like that. I like the end of an array being like a little cliff where you’re like, “I’m all alone!”

[00:07:31] SY: Yes. Okay. So then at that point, I’ve put 9 in its rightful place at the edge of the cliff as all 9 should be. And so I guess I’m done. Am I done being friends with 9?

[00:07:48] VJ: Well, yeah, you’re done being friends with 9 because you’ve taken it all the way home.

[00:07:52] SY: Yeah, home, that’s much better place to be. We’ve took it home.

[00:07:57] VJ: To the good place, to its happy place.

[00:07:58] SY: To the good place. There you go. There you go.

[00:08:01] VJ: But you’re done with 9, but you’re not done completely because after I first run, our list looks like 7, 4, 1, 9.

[00:08:11] SY: Okay.

[00:08:12] VJ: So the only thing that’s really sorted here is the number 9.

[00:08:15] SY: Okay, cool. So my new list as you said is 7, 4, 1, 9, totally not sorted but like in progress, right? We’re like in the middle of things.

[00:08:24] VJ: Twenty-five percent done.

[00:08:26] SY: That’s true, one out of four have been sorted, 25 percent done. Okay. So can we keep going? Can we do the next one?

[00:08:31] VJ: Yeah. Let’s do another one.

[00:08:33] SY: Okay. So excited. So, we have to start at the beginning again, right?

[00:08:42] VJ: Yes, we do.

[00:08:43] SY: Okay. So we start at 7 and then we’re like, “Seven, you are my new best friend.” I’m like a friend whore a little bit. I’m a friend slut a little bit, that’s okay. It’s okay. It’s fine. So I’m best friends with 7 and I’m going to say, “Seven, we’re going to take you home.” And I’m going to look at its neighbor 4 and I’m going to say, “Seven, are you bigger than four? Yes, you are. Swap time.”

[00:09:09] VJ: Yup. Now you got 4, 7, 1, 9.

[00:09:11] SY: 4, 7, 1, 9, okay. Still friends with 7, going to compare 7 with its neighbor, 1. Seven, are you bigger than one? Yes, you are swap time.

[00:09:20] VJ: Yup.

[00:09:21] SY: Now 7 is in the third place. So now we have 4, 1, 7, 9. Oh, see this is tricky. This is tricky because it’s like 9 is my ex now. So it’s like, You know what I mean? It’s like introducing your new boyfriend and ex-boyfriend.

[00:09:34] VJ: You’re like, “Don’t look at me.”

[00:09:36] SY: Yeah, that’s kind of awkward.

[00:09:37] VJ: But tell me if you’re larger or smaller.

[00:09:43] SY: Oh my God! I love that. Okay. So now I have to compare 7 and 9 and go, “Seven, are you bigger than nine?” No, you’re not. Twist.

[00:09:53] VJ: Yeah, that’s the first time that’s happened.

[00:09:55] SY: That’s first time, right? Okay. So then I go, “Well, this is your place. This is your home. So we’re not going to swap.” So this is a no swap situation. Okay. And then I guess I’m done with 7. I don’t need to look at 9 anymore, right?

[00:10:10] VJ: Well, yeah, it’s actually kind of cool because you are on your second pass. So you know that the element that you just looked at, because you took it through the whole set of items, you sorted it comparing it to every single element. You know it’s in the right place because you actually ended up with the largest element at the end.

[00:10:31] SY: That’s true.

[00:10:31] VJ: So you know you don’t need to look at it because the element you’re looking at.

[00:10:33] SY: I did a great job.

[00:10:34] VJ: Yeah, you did.

[00:10:35] SY: Yeah. Okay. Cool. So I’m done with 7, 9 I’ve already figured out. We don’t we don’t look back. We look forward, okay, on the Base.cs Podcast.

[00:10:46] VJ: We’re all about the future.

[00:10:47] SY: That’s true. And so we don’t need to worry about 9. So now my new order is 4, 1, 7, 9.

[00:10:57] VJ: Yes.

[00:10:57] SY: Okay. So like halfway there.

[00:10:59] VJ: Yup.

[00:10:59] SY: Okay. Now we start at the beginning again. This is our third run through, right?

[00:11:04] VJ: Yup.

[00:11:04] SY: It’s our third buddy. Okay. So now I am best friends with 4, 4 and I are like this, you can’t see because it’s a podcast, but I have my fingers crossed and we’re like this.

[00:11:13] VJ: Your real tight.

[00:11:14] SY: Just real tight. Just real tight. And so 4 I’m going to compare with its neighbor, 4 and 1, 4 is bigger than 1, so they’re going to swap time.

[00:11:24] VJ: Yep.

[00:11:25] SY: And then I’m going to say, “Okay, 4 we’re still like this. We’re still tight. So now I’m going to compare you to my most recent ex, 7.” And I’m going to say, “Four, are you bigger than seven? No, you’re not. Second plot twist.” So I leave 4 where it is.

[00:11:44] VJ: Yep. It’s already in the right place. You know by virtue of the fact that you’ve already done two iterations that you’re on the third element. So the previous two iterations would lead you to believe that the last two elements are in the right place.

[00:11:55] SY: That’s true. Okay. So I’ve already done two iterations, which means two elements are done. Now I’m at the end of my third iteration, which means my third element is done. Now I still technically have one more pass, right? Because I have like one more element that I technically haven’t checked yet. So now I can look at 1, 1 is now my new boo.

[00:12:15] VJ: Yeah, this relationship is not going to last that long, but okay. Keep going.

[00:12:21] SY: You don’t know, You don’t know anything. Okay. So number 1, I’m going to go, “Boo, let’s take you home.” So number 1, I’m going to compare you to your neighbor, which is 4. Oh, 1 is not bigger than 4, so there is no swap type. This is another no swap situation folks. And so I guess 1 is already home. You’re right. That was a very short-lived relationship. Okay. I think I’m done.

[00:12:53] VJ: You are done. You’ve got a sorted list. You got 1, 4, 7, 9 in order and you’ve got some other things too which is that you’ve kind of stumbled upon some interesting truths about bubble sort which is that you had four elements, right?

[00:13:07] SY: Yeah.

[00:13:08] VJ: You had to iterate through the set three times to sort completely.

[00:13:13] SY: That’s true.

[00:13:14] VJ: But if you had only let’s say instead of 9, 7, 4, 1, instead of 9, 7, 4, 1, let’s just say it was 9, 7, 4. Well, you would still need to sort twice, but you would only need to do two iterations for three elements.

[00:13:27] SY: Right.

[00:13:28] VJ: And if you just had 9 and 7, you just need to iterate once.

[00:13:31] SY: Yeah.

[00:13:32] VJ: So for four numbers, you needed to iterate three times. For three numbers, you need to iterate twice. For two numbers, you need to iterate once. So basically, there’s this pattern here, which is that in general it takes n minus one iterations in order to bubble sort your way through a collection of n elements.

[00:13:50] SY: Okay. And just to make sure, that’s because by the time I get to my last number, I’ve already sorted everything after it so there’s like no iteration that’s actually necessary.

[00:13:59] VJ: Yeah. Yeah. And I think this is actually, So I want to say this with a caveat which is that you don’t actually need to check the last few elements because it’s a little redundant, right?

[00:14:15] SY: That’s true. Yeah.

[00:14:15] VJ: So let’s say we did two iterations, right? We did 9, 7, 4, 1 we move 9 to the right spot and we move 7 to the right spot. So after those first two iterations through the array, we knew kind of that checking the last two elements was unnecessary because we had just put 9 in its right spot and 7 in its right spot. So it’s a little redundant because you know through the last two iterations that the last two elements were done correctly. That’s also like a pattern in bubble sort too where after let’s just say X number of iterations checking the last X elements in the collection is kind of redundant.

[00:14:56] SY: Yeah. So it’s interesting. It’s like with each iteration we get a little bit more efficient because we have less work to do.

[00:15:03] VJ: Yes. Yeah. I guess you could say that.

[00:15:05] SY: Would you not say that?

[00:15:06] VJ: No, I guess I’ve never thought about it that way, but you’re right. I think you’re right that in a way it’s like you have less to sort and because you have more knowledge about what you sorted and the way you’ve sorted you can kind of assume things.

[00:15:19] SY: Okay.

[00:15:20] VJ: And so the reason I think that this is interesting is because if you take that into account where you’re like, “Oh, I sorted the last two numbers. Don’t check the last two numbers.” You can optimize bubble sort and improve it. Because I’ll give you a little spoiler alert. It’s not very efficient.

[00:15:36] SY: Okay. My next question was going to be, this whole thing makes sense to me, I totally get it, I have a string of boos, they’re all home, it’s great, but I don’t see the bubble part of bubble sort. Why is it called bubble sort?

[00:15:53] VJ: This does actually have to do with your boos. So this is great. So it’s not that the number 9 was always destined to be like your first love. I didn’t know where that sentence was going, but it worked out.

[00:16:08] SY: It worked out great and I really appreciate it.

[00:16:10] VJ: It just so happened that that was the case because it was the first number and it was also the largest in the set, but imagine that it was a jumbled order and you had for example 4 and then 9. You would have started at 4 and said, “Oh, is 4 larger or smaller than 9?” It’s smaller. So then you would have moved on to the next element and you would have said, “Okay, now I’m going to look at 9.” And then you would have continued with 9 and said, “Oh, 9 is still the biggest, 9 is still the biggest,” and eventually what would have happened and if you kind of visualize bubble sort and you can look it up online later, you can look at visualizations of bubble sort where the number that is the largest in the first iteration makes its way to the end, then the second largest number makes its way to the end.

[00:16:50] SY: Yeah.

[00:16:53] VJ: And so the numbers, the largest numbers begin to sort of bubble up towards the end of the list where they belong, so the big numbers start to go home first and then the little numbers or the party animals who stay out late and they’re like, “I’m not going home to 7.”

[00:17:05] SY: One was definitely a party animal, yeah, I remember that.

[00:17:08] VJ: So that’s why it’s called bubble sort is because the large numbers began to bubble up to the end of the list. After each pass, the largest number that hasn’t been sorted ends up in the sorted section.

[00:17:20] SY: Okay. I buy that. That works. Okay. So you said something earlier about how bubble sort is not very efficient because I think I did a very efficient job, thank you very much, sorting all my boos. So what makes it so inefficient? What’s so bad about it?

[00:17:36] VJ: Well, I would like to point out that in the first pass we ended up with 9 in the right spot.

[00:17:43] SY: Yes.

[00:17:44] VJ: But none of the other numbers were in the right spot.

[00:17:46] SY: That’s true.

[00:17:47] VJ: And in the next iteration you moved another number over to the right spot, I guess you could say, but the rest of the numbers weren’t sorted and so what you’re basically having to do if you were coding bubble sort is you’re having to do kind of double the iteration so you can kind of think of it as like a loop within a loop or an iteration within an iteration, that’s not good.

[00:18:07] SY: True, because with each friend that I make, I have to check all the other friends.

[00:18:12] VJ: Yup, for every new boo you’re like, “Are you better than him? Are you better than her?” “I’m better.” All right, new boo and then you keep doing this comparison.

[00:18:20] SY: I love that. That is so me.

[00:18:26] VJ: But we can kind of talk about that in mathematical terms or rather in Big O notation terms.

[00:18:31] SY: Okay.

[00:18:32] VJ: So what we’re basically having to do is if we have n number of elements, we effectively have to take n number of iterations through the array because we’re going to end up looking at every element because we have to sort every element.

[00:18:44] SY: True.

[00:18:45] VJ: And within each iteration, as you mentioned, we’re going to check all the elements and numbered elements in the array because we’re comparing the element we’re moving with all of its neighbors as it moves along. So what you’re doing is making n iterations and n comparisons or checks. So that’s n times n steps in total to perform bubble sort and n times n is n-squared.

[00:19:14] SY: I remember this. I remember this is the bad one.

[00:19:19] VJ: Yeah, it’s the bad one. It’s back.

[00:19:20] SY: Oh, man! Oh, no!

[00:19:22] VJ: Well, this is what we call o of n-squared or quadratic runtime, which basically means like if our data set were to double from four elements to eight, then the amount of time that it would take for us to sort all of them would quadruple, which is why we say that it increases quadratically.

[00:19:39] SY: Okay. Well, that sucks.

[00:19:42] VJ: Yeah.

[00:19:43] SY: I was going to say I had the word bubble in it, I had my boos, I got to check them against each other, like it sounded like a great time and now you’re like, “No, actually it sucks.”

[00:19:53] VJ: Well, I actually think it’s not that bad if it’s a small data set.

[00:19:57] SY: Okay. It’s fine.

[00:20:00] VJ: I guess if you have for example four elements, then you would have to take 16 steps. Maybe that doesn’t matter. Maybe 16 steps isn’t a lot.

[00:20:07] SY: But if you got like a million, a million boos, can you even imagine juggling that?

[00:20:12] VJ: I couldn’t keep track of that, a lot of emotional energy and scheduling.

[00:20:16] SY: For them, yes.

[00:20:18] VJ: Anyways, that’s time complexity. Time complexity is where bubble sort really, really, really fails because it’s not good in terms of space complexity.

[00:20:28] SY: Oh, yeah. There’s two complexities, right?

[00:20:30] VJ: Yeah. Yeah. Well, space complexity is almost like when you think about how bad it performs time wise, you almost don’t even care about space complexity because you’re like, “Why would I even bother?” But it is important to consider both and the interesting thing is that it doesn’t take a large amount of memory in the sense that all you really need in terms of like variables or memory to hold onto things while you’re doing this sort is just like a couple pointers, a couple references.

[00:20:56] SY: Okay.

[00:20:57] VJ: So we can say that it has o of 1 or constant space complexity. So that’s nice.

[00:21:03] SY: That is nice because we’re doing it everything in place.

[00:21:06] VJ: Yes, but it’s going to take you a long ass time. So maybe don’t do it.

[00:21:10] SY: Still don’t do it. But if you have to, at least you don’t need more room.

[00:21:14] VJ: Trying to look on the bright side here.

[00:21:16] SY: Try to find the silver lining.

[00:21:18] VJ: There’s one other bad thing that I want to say about bubble sort, but there’s a clever way that you can fix it, which was maybe obvious, which is that if you’re running bubble sort on a list that is already sorted you’re still going to check everything by default which is kind of silly because you’d be like, “Let me compare 9. Let me compare this. Let me compare that.” And then you’re like, it’s already sorted. So one optimization you can do for that is you can just assume that if you have gone through an iteration and never swapped any element, then you know that I haven’t swapped anything. So everything is in its correct order so that means the list is already sorted and you can sort of short circuit out of bubble sort.

[00:21:59] SY: I love that.

[00:22:00] VJ: Yeah, you can just be like, “Oh, no swaps.”

[00:22:03] SY: I love that. See? I had hope. I believed.

[00:22:05] VJ: It’s a redeeming quality, I guess.

[00:22:10] SY: Nice Okay. So basically bubble sort is kind of crappy, but that’s okay. You can still organize your boos with it. It just might take a really long time, but it won’t take up any space which is good because you got to keep your boos in their place.

[00:22:27] VJ: Yeah.

[00:22:30] SY: That is the lesson today.

[00:22:32] VJ: My main take away from it also is like you aren’t ever going to probably write it. You don’t want to use it. If you see it, it’s bad, run away, and it might come up in a computer science course or whatever because people like to use it to be like, “Hey, look at how bad it is,” which is I guess what I just did.

[00:22:48] SY: Yeah. Yeah. Okay. Cool. Okay. I have to say it is not as scary as I was afraid it was going to be. I really thought it was going to be like some… because I hear about it a ton. You know that’s going to be some scary thing, but actually it’s not that bad. And that’s the end of today’s show. If you liked what you heard, please leave us a review and make sure to check out Vaidehi’s blog post. Link is in your show notes. Also want to give a huge thank you to Linode for sponsoring the show. Try their powerful servers built for all your infrastructure needs. Getting started with a shiny new server takes less than one minute so you can get up and running in no time. Get a $20 credit by using the promo code CodeNewbie2019. Just go to linode.com/codenewbie for more info. Also want to give a huge shout-out to DigitalOcean. They are the easiest way to deploy, manage, and scale your application. Everything about it was built with simplicity at the forefront; setting, deploying, even billing. Try DigitalOcean for free by going to DO.co/codenewbie and get $100 in infrastructure credit. Link is in your show notes. Vaidehi, you want to say goodbye?

[00:23:54] VJ: Buh, buh, buh, buh bye!

Bloopers

[00:23:57] SY: Thanks for listening. See you next week. So now after my second swap, my new order as of now is 7. Oh, I got to burp, hold on… That was a bubble. Okay.

[00:24:17] VJ: You know that was the best episode for that to happen in.

[00:24:19] SY: Right? It happens every episode, but that one was like appropriate.