Sorting Types

[00:00:00]
>> Bianca Gandolfo: So sorting, we talked about a couple different searching algorithms, linear search, binary search. Now we're gonna talk about another hot topic in the algorithms world, which is sorting. Searching and sorting are pretty time-intensive operations, and they're also core to a lot of the processing that we do in the day to day on the web, right?

[00:00:20]
We have Google search and we want to sort our photos by time stamp and things like that. And you can imagine that when we're dealing with these kinds of problems, the data sets that we're working with can be really, really large. And so there's been a lot of studies done on improving sorting and searching.

[00:00:38]
And we'll be doing a lot of work with that when we get to the data structures part, cuz a lot of our searching is combined with a particular data structure and how you get to your solution. So for binary search, right, we have a binary search tree that goes nicely with it.

[00:00:57]
And so we'll keep building on these topics in mastering them together. So for sorting, there are two main types of sorting that we're gonna talk about. We have naive sorts, naive sorts are going to be quadratic time, right? We're going to compare everything to everything at some point.

[00:01:18]
And you're gonna imagine that these are gonna have two loops involved. Then we have our divide and conquer sorts, we're gonna talk about merge sort today, we're not gonna get to quick sort, but these are gonna be n log n. So the reason that sorting is always going to have some, and for comparison sorts, there are non-comparison sorts out there that we won't talk about but you can research, those are pretty interesting.

[00:01:44]
You always are gonna have to compare one item to another at some point. So it's never gonna be less, because we have to look at everything, you can't ever be less than linear, right, same with searching. Actually no, that's not true, same with,
>> Bianca Gandolfo: Actually none of that's true.

[00:02:06]
So for sorting, you have to look at everything. And so it can never be in your head, right, you have to uncover each thing to sort it. So it could never be less than that, but really, the best you can do is n log n. And that's what these divide and conquer algorithms, where we have to look at everything, but we don't have to compare everything to everything else to sort it.

[00:02:30]
Where these naive sorts, that's the basis of them. So we have bubble sort. Bubble sort compares adjacent indices and kind of bubbles up the larger number. And so, you can see here, we can start with this unsorted. We compare 5 to 1, okay, 5 is bigger, we swap it.

[00:02:58]
And then we do the next one, 5 to 4, we swap it. And then you keep going, and keep swapping and swapping until you can see, compare 1 to 4, no swap, and you can compare 4 to 2, swap, etc., until we finally reach our solution. So this is a common naive sort.

[00:03:20]
A couple other ones are insertion sort, which you basically take another empty array, and then you choose. Or no, this is selection sort, where you choose the biggest one. Or you actually, you could choose the smallest one and then you push it into that array. And then you choose the next smallest one, you push it to that array.

[00:03:41]
And then it builds a new array with the sorted values, thank you. Conversely, mergesort and quicksort are a little harder to reason about because we are going to be recursively handling the sort. So the merge, with the merge sort, we take sorted lists. So we have to start with a sorted list, and then we sort two sorted lists.

[00:04:14]
Let me show you the chart. So the first thing you do, you're gonna divide, divide and conquer. So let's do the divide steps. We start with an unsorted list. You divide it, divide it, and divide it until it's sorted. When is it sorted, when it's a list of one.

[00:04:28]
So you can assume that any list of one is gonna be sorted until you start there. Then, you're going to merge each sorted list. So you're going to choose each one. So this one is now sorted, right, you put 27 first and then 38. And then so on and so forth, until you get your sorted list.

[00:04:53]
And so what this does is, you don't have to compare 27 to 10, for example, until you get down here. And so you're not having to check in a quadratic way. I wish I had a diagram of how many columns it would be for bubble sort to get to where you need to go.

[00:05:23]
But you can see that we're chopping the problem in half each time. That's gonna be your logarithmic part. However, we still need to do this final loop here, which is gonna be the linear. So you can kind of see how it's cut in half, that's the log part.

[00:05:41]
And then the final merge, you can kind of think of it as the linear part, and that's the n log n of mergesort, mm-hm.
>> Speaker 2: So why do we step through the second and third steps of this tree? Why don't we go straight from the top to add into one value of these and then keep?

[00:06:03]
>> Bianca Gandolfo: Mm, because the nature of recursion, that's why. Cuz I can. So, you could,
>> Bianca Gandolfo: Could you do that? I don't know, I've never seen a solution like that. That would be interesting, but essentially you divide it. So you're saying start with the divided part? So the thing about, I'll show you when we get to the pseudo code, because I'll show you where it pauses and then it continues.

[00:06:45]
And then, you'll see how this kinda plays out in the code. But I can't imagine it playing out where it's already divided. Although that would seem like an optimization if you could. So that's a cool idea.