Description

How does quicksort perform? And how do variables, like the pivot number, affect it? We walk through three examples to find out!

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Pivoting To Understand Quicksort [Part 2] from her basecs blog series.

Transcript

[00:00:00] SY: If you haven’t yet gotten your tickets for Codeland, you totally should. It’s our annual conference about all the wonderful things you can do with code. And besides great food, great talks, and great people, this year we’re offering complimentary on-site childcare. So bring your babies with you and see you there. For tickets, go to codelandconf.com.

[00:00:23] (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:30] VJ: And I’m Vaidehi Joshi, Author and Developer.

[00:00:33] SY: And she is the brilliant mind behind the Base.cs Blog Series. Today we are continuing our conversation on…

[00:00:39] VJ: Quicksort.

[00:00:41] SY: This season of the Base.cs Podcast is brought to you by Linode. If you’ve got a personal project, a small business or a big business with lots of data, Linode offers you a 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:17] It’s also brought to you by Square. If you’re designing a website or building a mobile app, you’re probably going to want to take payments at some point. Square APIs allow you to easily implement their payment form on your website. And with their In-App Payments SDK, you can add it to your mobile app too. You don’t have to worry about dealing with PCI compliance because they’ll take care of that for you. Don’t let anything come between you and your money. Start building with Square over at squareup.com/go/codenewbie.

[00:01:50] SY: Okay. Let’s do a quick recap of quicksort. What is it?

[00:01:54] VJ: So quicksort is probably one of the most widely used and researched algorithms. Actually, don’t quote me on the research part, but it’s well written about, let’s say that.

[00:02:06] SY: It’s got some clout.

[00:02:07] VJ: It’s definitely got some clout and the reason is because of the fact that it is pretty efficient given sorting algorithms and we’ve talked a lot about sorting algorithms in general.

[00:02:19] SY: Yeah. I have not been impressed, by the way, with some of these sorting algorithms. I’ve been underwhelmed.

[00:02:24] VJ: It’s gotten steadily better, right?

[00:02:26] SY: It has. It has we’re going in the right direction. Yes.

[00:02:29] VJ: Yes, exactly but to answer your actual question, which is what is quicksort, it’s a sorting algorithm that uses a technique of finding a pivot element within a collection and it does the work of sorting by basically partitioning or dividing the collection according to the pivot element. So we choose a pivot element, we partition the collection around the pivot element, and we move smaller elements before the pivot and larger elements after, and we continue to do that recursively until the entire collection is sorted.

[00:03:02] SY: Yes. And I remember that pivot element being super, super important

[00:03:06] VJ: Yes, it is. It is basically the cornerstone or the crops of the entire algorithm. It’s so important.

[00:03:13] SY: And I assume that which one we pick is probably a factor in how good the sorting algorithm is.

[00:03:19] VJ: Yes. The decision we make in how we go about choosing a pivot is going to kind of like create a domino effect of the quicksort algorithm doing what we expected to and what we wanted to do and what it’s known to do. Or if we go to the other direction and we could find ourselves kind of back at square one, and when I say back at square one, I mean just as inefficient as the other algorithms we looked at.

[00:03:44] SY: Oh, like bubble sort.

[00:03:46] VJ: Yeah. I know.

[00:03:48] SY: Or worse. Okay. Okay. So it really is that important, like it’s not just, "Oh, it’ll be a little be a little faster, a little slower, like it could really change the whole game if we pick the wrong pivot number.

[00:03:59] VJ: Yeah, it could. And I think the reason why, if we think back to the definition I just kind of used to summarize quicksort, we’re using a pivot to partition our collection and we’re saying everything that’s smaller is going to go to the left of it and everything that’s larger is going to go to the right of it. Well, if we pick a pivot element that isn’t really in the middle of the dataset, then we could end up with very unequal partitions and that will end up with us having a quicksort algorithm that doesn’t perform the way we want it to.

[00:04:34] SY: Okay.

[00:04:35] VJ: What we want to do is choose a pivot that falls close to the median of the dataset that we’re trying to sort.

[00:04:42] SY: Okay. I think that makes sense because basically what you’re saying is if we have numbers 1 through 10, right? 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let’s just assume they’re all jumbled up. We want our first pivot element to be like number 5 or number 6, like basically right around the middle because then we have two even sections on either side.

[00:05:05] VJ: Yes.

[00:05:06] SY: Because the end of the whole pivot element story is that let’s say if we pick number 5, number 5 will end up in its proper place, which is right in the middle. So now we have two halves that we can sort at the same time.

[00:05:21] VJ: Yeah. And if we kind of want to do a thought experiment about a collection with the numbers 1 through 10.

[00:05:27] SY: Yeah.

[00:05:28] VJ: If we choose 10 as our pivot, we’re going to be comparing 10 to way more elements than we would if we picked a number that was in the median because every single number that we compare 10 to we’re going to check is it larger or smaller because 10 is our pivot and numbers that are larger will go to the right, numbers that are smaller will go to the left. But if we pick the largest number, well, now everything is just going to the left and we’re going to compare it.

[00:05:54] SY: We basically didn’t do anything.

[00:05:55] VJ: Yeah. That’s a good way.

[00:05:58] SY: It’s like nothing happened.

[00:06:01] VJ: And then we’ll pick another pivot, but it’s just kind of like, “Oh, well, we did a whole pass for no good reason.”

[00:06:06] SY: Yeah.

[00:06:06] VJ: And so if we pick a pivot that isn’t at the median, we end up comparing it probably to a lot of the elements, sometimes even all the elements in the dataset. And by doing all these comparisons, comparing the pivot to every number in the dataset, we actually end up running an algorithm that runs in quadratic runtime. So like N squared, O of N squared in big O context.

[00:06:28] SY: Well, that’s bad.

[00:06:29] VJ: Yeah. It is bad.

[00:06:31] SY: No, quicksort. Don’t. Stop it.

[00:06:34] VJ: It’s taking after bubble sort and some other algorithms that we talked about.

[00:06:37] SY: Stop hanging out with bubble sort.

[00:06:40] VJ: Such a negative influence.

[00:06:41] SY: Bad influence. God. Okay. So in that example where we have 1 through 10, it’s all jumbled up and we start with 10 as our pivot element and then everything is obviously less than 10, so it all goes to the left and it’s like we didn’t do anything. That totally makes sense to me why that is terrible just logically, but I want to understand how we actually get to the N squared big O notation. Like how do we get to that, that level of badness? Can we walk through an example and kind of count the steps?

[00:07:13] VJ: Well, I have an idea. How about we just do a completely sorted list?

[00:07:16] SY: Okay.

[00:07:17] VJ: What happens, for example, if we run quicksort on a collection that is 1, 2, 3, 4, 5? So it’s completely sorted.

[00:07:23] SY: Okay. Okay.

[00:07:24] VJ: Because I think this is actually pretty interesting too the way that quicksort behaves.

[00:07:28] SY: Okay. So completely sorted list: 1, 2, 3, 4, 5. We’re still going to run the quicksort algorithm on it. And the example we’re working with is what happens when you start with “a bad pivot element”. So let’s start at the end, let’s start with 5. If 5 is our pivot element, what do we do now? What happens?

[00:07:47] VJ: Well, we’re going to compare all the numbers to the pivot in some way and we won’t get into the details of all this since we’ve kind of covered that in a previous episode. But what we will do is we will compare five to every number that needs to be compared to the pivot. So we have 1, 2, 3, 4, and we will do nothing in terms of moving the pivot anywhere else because the pivot is already the largest number. So what we’ve basically done is we have compared the pivot to every other number in the list.

[00:08:17] SY: And then done nothing? So we’ve done like five moves and then at the end of it nothing has really changed.

[00:08:24] VJ: Exactly. And we’re running quicksort on this whole sorted list. So we’re going to repeat the same thing again recursively. And if we implement it again recursively, 4 will be the next pivot and we’re going to compare 4 to all the other numbers in the subset list. So we’ll compare 4 to 3 and 4 to 2 and 4 to 1 and we’re going to do nothing again because 4 is already in the right place. And if we continue doing all of this, the number of moves that we’re actually going to do is going to be N times N or N squared where we have five elements and we’re making five moves. So 5 times 5, 25. That’s where that quadratic behavior comes from and that’s the same thing we’ve seen in previous algorithms where we found ourselves comparing one number to everything else and continuing to do that. And that’s pretty bad if we go from 5 elements to 50 or 500 or honestly even 10. We didn’t even go through all five. We just started going through the example and I don’t even want to continue going through the rest of numbers.

[00:09:30] SY: I don’t even like this game anymore. Okay. So I get that if we compare, if we start with 5, we compare 5 to every single number, it takes five moves before we’re done with that round. But then we move on to the next number, which is 4, the number of comparisons that we do it’s not 5 anymore, right? I think it’s only 4.

[00:09:53] VJ: You are right. That is very true. I got carried away with one of my 5s.

[00:09:59] SY: Those 5s will just take you for a ride.

[00:10:02] VJ: You’re right. We’re not actually going to deal with number 5. So the number of elements is now 4, not 5. So I guess the next round you would be comparing and checking the number 4 with 3 other elements.

[00:10:15] SY: Okay. So then in that case, this example doesn’t work out exactly to N squared. It’s almost like it’s approaching N square, but it’s not like quite there. Does that still count as N squared or how do we reconcile that?

[00:10:30] VJ: Yeah. And I would say that it’s approaching N squared when it’s that situation. I guess if you look at the subset, each one of the recursive bits like whether you’re comparing 4, 3, 2, 1 or 3, 2, 1 or 5, 4, 3, 2, 1, the reason that we say that it is quadratic in that situation is because you are comparing an element with all the other elements in the list and if you were going to code it, it would be a double loop, right? Because we say for each element, compare it to the other elements that are in the list. Now for the recursion, for the next sub list, for that element, for that pivot, compare it to the other elements. So that’s what makes it O of N squared. So I like that phrasing that you used, approaching N squared. We can think of it that way, but the more important thing, the point that I really want to drive home is that when you don’t pick a pivot that is in the median of the list, well, now you’re doing a bunch of extra checks that are unnecessary and not helping you and are going to take more time.

[00:11:33] SY: They are not doing anything, not pulling their weight or anything. Okay. So for this example with 1, 2, 3, 4, 5, we had kind of like two things going… I don’t want to say against us. But that worked out kind of silly. The first is that it was already sorted, right? Like what was going to happen? Best-case scenario, worst-case scenario, nothing happens. And then the number 5 that we picked we’ve decided is a bad pivot element to pick and we saw that in action, but I’m curious. What does it look like if we have a not sorted, a totally jumbled up list, but we still picked a bad pivot element? So if we did for example 4, 3, 1, 2, 5, we still started with the number 5 as our pivot element. Would things be any different? How would that look?

[00:12:24] VJ: Well, in this situation, it’s not like our whole list is sorted as you mentioned.

[00:12:27] SY: Right.

[00:12:28] VJ: But if we go with our same fundamental rule of pick the last element to be the pivot, well, now we’ve picked 5 and it happens to be not anywhere near the center of the list. It’s actually going to be at one end of the list. It’s the largest. So you’re going to end up doing another pass where you’re going to compare 5 to everything and now you’re going to end up with a subset on the left side of everything that’s smaller than 5 and what you’ll end up doing is approaching N squared operations where you are going to compare.

[00:12:58] SY: Still?

[00:12:58] VJ: Yeah. You’re going to compare at least one element to all the other elements in the list, which is not great because it’s not helping us and we are going to end up with a completely unequal set of partitions. One partition is going to have all the numbers and the other partition will have nothing because nothing is bigger than 5 in this list.

[00:13:15] SY: Okay. So because we started with number 5, the biggest one, in our first pass through, we’ll be in the exact same situation. So we basically, like the whole… because this is one of those divide and conquer algorithms, right?

[00:13:30] VJ: It is.

[00:13:31] SY: So basically we’re not dividing anything.

[00:13:34] VJ: We’re dividing it in really silly way that is just not good.

[00:13:37] SY: Yeah. It is. Yeah, like we cannot divide and conquer in this, at least in the first round. We can’t do that. So we’re still in that bad situation. Okay. I buy that. I guess the good thing is the next number over is 2 and 2 isn’t exactly in the middle, but it’s a little bit more in the middle. So we can probably do a little bit more dividing and conquering at least on the second round.

[00:13:59] VJ: Yes, but you are still going to be doing the dividing and conquering on only one partition of your original collection, right?

[00:14:06] SY: Right, because we weren’t able to break it up into pieces.

[00:14:08] VJ: Yeah, exactly.

[00:14:10] SY: Oh, okay. So I see how that first one can kind of set you up for better or worse.

[00:14:17] VJ: Yeah. I think the moral of the story here kind of is, you know, in the previous episode, we’re like, “Oh, we’ll just pick the last one. That’s fine.” And in this episode, we are like, “Oh, I’ll just pick the last one, but wait. Do I want to pick the last one? Hang on.” Because we need to be the center of the list.

[00:14:34] SY: Yeah. Yeah.

[00:14:34] VJ: So it’s very important for us to pick a smart pivot.

[00:14:37] SY: Okay. So let’s say we picked the middle number and says, “Let’s jumble them all up again and this time we’re going to pick 3 as our pivot element.” This time the set is 4, 1, 2, 5, 3. So 3 is at the end.

[00:14:52] VJ: We’re picking the number right in the middle.

[00:14:55] SY: Yes. Nailed it.

[00:14:55] VJ: This is great. We haven’t done that yet.

[00:14:57] SY: We have not done that. We’ve been just dealing with 5 over there, just being all kinds of difficult and now moving on to something better. Okay. So 4, 1, 2, 5, 3, we’re going to start with 3, our pivot element, our glorious middle number, our pivot element. How do these change things for us? So initially, when we did 1, 2, 3, 4, 5 and even when we did 4, 3, 1, 2, 5, when 5 was the pivot element, the first iteration took us five steps and got us nowhere, right? Okay. So is that going to happen? And if so, how is it going to happen? Go.

[00:15:35] VJ: So what we know about quicksort is that we’re going to have a left reference and a right reference. So once we choose our pivot, the number 3.

[00:15:45] SY: Yup.

[00:15:46] VJ: So we chose our pivot. We’re like, “All right, step aside. We’re going to keep a left reference, like a left side of the list and a right reference at the right side of the list.” So in our situation, what we’re really dealing with are the numbers 4, 1, 2, 5 and then our pivot, 3. So we have a left reference at the number 4 and a right reference at the number 5 and we basically are going to look at the left reference compared to the pivot and maybe move our pointer and look at the right reference and compare it to the pivot and maybe move our pointer. So in this situation, we’ll say, “We’ll look at the left reference,” and we’ll say, “Are you less than the pivot? No, you’re not less than the pivot. You’re the number four. Well, I’m going to keep you right there.” And we’re going to look at the right reference and we’re going to say, “Are you less than the pivot?” The right reference is not less than the pivot. So in this situation, because the right reference is greater than the pivot, well, we’re going to move on and increment it. And so now our left reference is the number 4 and our right reference is the number 2. And we’ll do the same thing again where we’ll compare our left reference to the pivot and the right reference to the pivot. And when we compare the right reference this time, we’ll see that the right reference is actually smaller than our pivot. Two is less than three. So this is when our swap happens.

[00:17:03] SY: Something interesting is going to happen.

[00:17:06] VJ: Exactly. When the left reference is greater than the pivot and the right reference is smaller, you know that you can have a swap. So in this situation, 4 is greater and 2 is smaller, which means, “Oh, we have two items that are going to be in the wrong sub list. So let’s swap them.”

[00:17:21] SY: Swap them.

[00:17:22] VJ: We basically did like one swap so far and we’re not even done going through our sub list yet, right? We’ve only looked at a couple of numbers.

[00:17:30] SY: That’s true. We’ve like started the sorting. We actually started the sorting process, like we technically started it a while ago, but like things are moving, like we’re making progress in our sorting process because we are able to do a swap.

[00:17:42] VJ: And now our list reads 2, 1, 4, 5, and then 3.

[00:17:47] SY: Okay.

[00:17:48] VJ: And so we can kind of already see that like this is starting to look a little more sorted and what we’ll end up doing next is our left reference is going to increment and now we’re going to be looking at 1 and 4.

[00:18:02] SY: Yup.

[00:18:03] VJ: You know, we’ll go through the same process and we’ll say, “Oh, well, 1 is in the right, it’s in the correct place because it’s less than 3 and 4 is in the correct place because it’s greater than 3 and now we’ll get to the point where our references, our pointers are going to cross over.” And when you get to the crossover point, you know, “Oh, my left reference is now past my right reference and now I’ve looked through all the elements.” So the only thing left to do is really deal with the pivot. And so in this situation, we’ll recall that once the index of our left reference is greater than or equal to the index at the right reference, we’re going to swap the pivot with the element at the left reference.

[00:18:44] SY: Yeah.

[00:18:44] VJ: So because we incremented from 1 over to 4 and we moved 4 over to 1, so what I mean by that is we move to the left reference from 1 to 4 and the right reference from 4 to 1, we’re going to swap the reference of 4 with 3. So that basically means 2 and 1 stay in their same spot, 4 and 3 are pivot swap and now we have 2, 1, 3, 5, 4.

[00:19:11] SY: Okay. So now we are at 2, 1, 4, 5, 3. Can I attempt to move things now?

[00:19:19] VJ: Yes. You want to do some swapping? Okay.

[00:19:20] SY: Yes, I want to do some swapping. I want to get down this. Okay. So 2, 1, 4, 5, and then 3. Okay. So we just swapped 2 and 4. So now the left reference is at my 2, the right reference is at my 4. Now we’re going to increment the left reference, which is going to go to my number 1 and it’s going to compare it to my pivot element which is 3 and it’s going to say, “Is this number, the number 1, less than 3?” It is less than 3 so there’s no swapping to do. Everything is fine at this point. So now my left reference is at 1, my right reference is at 4. Now the reference for each is now going to increment, which means my left reference is going to now be pointing to 4 and my right reference is going to now point to 1.

[00:20:11] VJ: Can I actually interject here?

[00:20:13] SY: Oh, yeah.

[00:20:13] VJ: Just for this one thing. You don’t even have to move your right reference at all because the moment that you are left reference is greater than or equal to your right reference. That’s when all the fireworks go off and you’re like, “Oh, it’s time!”

[00:20:26] SY: So our final outcome, I guess, at the end of the first run through is 2, 1, 3, 5, 4.

[00:20:36] VJ: Yeah. And now we have two sublists to deal with and they’re not completely sorted. That’s okay. We have 2 and 1 on the left and then 5 and 4 on the right, which is a lot better than when we had a whole bunch of numbers and then our pivot and nothing changed.

[00:20:50] SY: Yeah, because that was the whole point of going to this example, right, was to figure out, “Did it matter that we picked the number 3?” And it did for two reasons. Number one, we moved some of the other numbers around. So 2, 1 being on the left, 5, 4 being on the right. We’ve made some progress in terms of our actual sorting, but now we have these two sub lists because we can do 2 and 1 and then we can compare 5 and 4 and we can do them at the same time.

[00:21:15] VJ: Yeah. And also, like even when we had the large number that was not the median, we did have two sub lists, like we had a sub list with four elements and a sub list with nothing.

[00:21:25] SY: Yeah.

[00:21:25] VJ: It was the fact that it was just so imbalanced, right? They weren’t equal. And in this situation, we have two elements in both sub list. So they’re pretty equal and even if it was like 2 and 3, that’s still way better than 4 and 0. And so we kind of have this nice little balance, like the scales are balanced on either side of our little pivot.

[00:21:45] SY: So if we were to finish off this quicksort with the 2, 1 and then the 5, 4, it’s pretty obvious what we’re going to end up doing. We’re going to end up switching to 1 and we’re going to end up switching 5, 4. So we can very easily count the number of steps and the number of moves that we needed, right? We needed three rounds, I think, right? We had basically pivot element 3 and then pivot element 1 and 4, if we decide to pick those, and then we’re done. We don’t even need to use all of our elements as pivot elements to be done with the sorting.

[00:22:22] VJ: Yeah, because after the next round, if we sort with 1 as the pivot and 4 as the other pivot for the two sub lists, we’re going to end up with two sorted lists because they’ll just have one element each in it.

[00:22:33] SY: Right.

[00:22:34] VJ: And then we’re really done with breaking up things and finding a pivot.

[00:22:38] SY: Yeah. So by having a better pivot number, we have more sub lists, which means we need fewer iterations to sort our elements.

[00:22:49] VJ: Yes. And asterisks on that. It’s the fact that we have equal sublists too is also important.

[00:22:54] SY: Right. Right.

[00:22:55] VJ: We have more sub lists that are equal rather than sub lists that are totally unbalanced.

[00:23:01] SY: Okay. Okay. So what is the performance of this? If we picked the correct, the best pivot element, and we had balanced sub lists all the way down, like what is the best performance that we can get out of this quicksort?

[00:23:16] VJ: So when our pivot is close to the median, as you just explained, then our average runtime for an unsorted list using quicksort is O(n log n), which we also known to be called linearithmic time.

[00:23:32] SY: You mean log N linear, I think, is what you’re trying to say.

[00:23:35] VJ: Yes. And in your dictionary, yes, for everyone else.

[00:23:37] SY: Yes. It’s so much better than linearithmic. Look, I’m going to win this. Somehow, somewhere I’m going to win this argument. I really am. Okay. So far, that’s been the best one that we’ve seen for a sorting algorithm.

[00:23:52] VJ: So it is the best runtime we’ve seen for a sorting algorithm. I do want to bring up one little character, which is merge sort. Merge sort and quicksort have equal running times in the sense that they are both O(n log n) and it kind of makes sense because they’re both divide and conquer, they’re both recursive, they kind of approach the problem differently, but they’re both very…

[00:24:15] SY: Have the same mission.

[00:24:16] VJ: Yeah, they’re on the same track. They’re walking on their own paths.

[00:24:21] SY: Walk on the same path. Yeah.

[00:24:22] VJ: They’re walking hand-in-hand. How about that? They’re just like…

[00:24:24] SY: Okay.

[00:24:25] VJ: That’s a cute image.

[00:24:26] SY: Right. But they’re looking in different directions, maybe.

[00:24:28] VJ: This seems like one of them is going to lead the other one off a cliff.

[00:24:31] SY: Yes.

[00:24:34] VJ: But sure. Yeah.

[00:24:35] SY: They have issues in their relationship. They’re working it out. It’s fine.

[00:24:37] VJ: They’re both on the same page as far as being linearithmic in their runtime.

[00:24:42] SY: Okay.

[00:24:43] VJ: This is the best we’ve seen so far. We have seen it once before which is with merge sort.

[00:24:47] SY: So quicksort is interesting because it sounds like there are many things we can do that will either make it really good or not so great. So what are some things we can do or we should keep in mind to increase the performance of our quicksort?

[00:25:02] VJ: Number one, if we know that we’re going to be dealing with mostly sorted list or even totally sorted list, we probably don’t want to use quicksort because we know what’s going to happen. That is one way that you can optimize is to not use that algorithm when we know it’s going to perform poorly. The other thing we could do is we could actually run quicksort, run it recursively on both of those partitions that we are talking about since we know we’re going to have two sub lists. We can run them in parallel because we want to pick a new pivot and sort through them using the same quicksort algorithm. We know we want to do that. So what we could do is spawn two different tasks and basically run a quicksort algorithm on both partitions, on both sub lists at the same time. So this is called parallel quicksort, which we aren’t going to get into, but you are using the same amount of space as a normal quicksort algorithm, but you’re using half the amount of time because you’re not running one-half and then running the other half. You’re just running the two halves at the same time, which is kind of cool.

[00:26:07] SY: Yeah. Nice.

[00:26:08] VJ: But I think also the one that I want to point out because we’ve been talking a lot about picking a pivot that’s a median, probably like a very high gain, but low investment optimization we can make is…

[00:26:23] SY: I like this.

[00:26:24] VJ: Is just don’t blindly pick the median as the last element, maybe look at the last few elements. So we could look at the last like four elements and be like, “Which of these is the median?” If you know what the dataset is going to be, like if you know it’s between one and a thousand. If you vaguely know what the median should be, there’s no reason that we have to necessarily pick the last element because we know that that could be bad news for us so we can look at the last four and be like, “Okay, this is probably the best thing to pick as the pivot because it’s about in the middle of the dataset.”

[00:26:56] SY: Okay. That’s really interesting because now I’m thinking if I know that I have a thousand numbers, right? Meaning like one to a thousand, so I can say, “500 is going to be my pivot number.” So I can do maybe a different like a prep step before my quicksort, right? Like I can go, “Find number 500.” And once I have that, then I can plug that into my quicksort algorithm and use that as my pivot element.

[00:27:25] VJ: I wouldn’t say it’s as simple as find 500 because in order to find 500, you’re going to have to go through the list and find it.

[00:27:32] SY: That’s true.

[00:27:32] VJ: And so now you’re searching through the list and be like, “Where’s the median? Where are you? Where are you?” But I guess what I’m trying to get at is that if we look at the last three elements, that doesn’t take us that much time.

[00:27:44] SY: Okay.

[00:27:44] VJ: We’re not going to be searching through a dataset, but we’re just kind of picking and we’re saying like, “Pick five elements from my list.”

[00:27:50] SY: It was here.

[00:27:50] VJ: Yeah, and be like, “Which one of you is the best one for the job?”

[00:27:53] SY: Okay.

[00:27:53] VJ: Rather than finding that element because maybe you also are like, “Oh, well, let me look for the number 500.” And what if it’s like not there? Maybe it’s numbers one through a thousand, but five hundred doesn’t even exist.

[00:28:04] SY: Oh, no!

[00:28:04] VJ: Like we can’t even rely on that.

[00:28:07] SY: Okay. I take back my plan.

[00:28:09] VJ: It was a good idea though.

[00:28:10] SY: Thanks. I tried. It didn’t work though. Okay, so handful of last elements, low investment, potentially high up. Okay. I dig it. I’m cool with that. And that’s the end of today’s show. If you like 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 shout out to Linode for sponsoring the show. Linode is giving you a chance to try their powerful servers built for all your infrastructure needs. They’ve got nine data centers worldwide with new data centers opening this year in India and Canada. Getting started with a shiny new server takes less than one minute so you can get up and running in no time and you can get a $20 credit by using the promo code CodeNewbie2019. Just go to linode.com/codenewbie for more info. And want to say thank you to Square. Square has APIs and SDKs to make taking payments easy whether you’re building a mobile app in iOS, Android, Flutter, or React Native. If you want to embed a checkout experience into your website, it’s super easy. Square has processed billions of transactions so you know it’s tried and true. Start building with Square over at squareup.com/go/CodeNewbie. Vaidehi, you want to say goodbye?

[00:29:28] VJ: Bye everyone.

[00:29:29] SY: Thanks for listening. See you next week.