Transcript from the "Review: Elementary Sorting" Lesson
>> Bianca Gandolfo: We're going to quickly go over our elementary sorting algorithms. These are comparison sorts. So bubble sort compares adjacent elements and bubbles up the largest through each iteration. Then we have our insertion sort. It takes the first element, then sorts the rest of the array around that element.
[00:00:18] Inserting it into the right place. Selection sort is going to keep selecting the smallest element until the array is sorted.
>> Bianca Gandolfo: So, these are elementary sorts. These are sorts that you could probably come up with on your own, right, if you had to.
>> Bianca Gandolfo: But they're terribly slow.
[00:00:39] And that's okay for small input sizes. But, important to know. Cool, we also learned some vocabulary. So we have a stable algorithm. It's going to preserve the original order when values are the same. And then we have adaptive, which means it's going to become more efficient as the list is nearly sorted.
[00:01:02] And these are some things to consider when you're choosing the proper sorting algorithm for your use case.
>> Speaker 2: Can I aks you a quick question?
>> Bianca Gandolfo: Yeah, absolutely.
>> Speaker 2: We've referred to the better sorting algorithm as optimized. But would that be the same, adaptive and optimized? Or are they different?
>> Bianca Gandolfo: So when we optimize an algorithm, you can optimize any algorithm, not just a sorting algorithm. Like, making something adaptive could be an optimization, but they're not exactly the same. Does that answer your question?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Cool. Good question, though. So here's our bubble sort. This is our solution from yesterday.
[00:01:48] We set our wall at the end of the array. That's going to be considered our first sorted element. Alright, we're going to move up our first sorted element to there. And as we loop through, we're going to compare adjacent elements and continue swapping them. And then once we get to the end, our walls going to move over one.
[00:02:11] And at the end, we're going to return our array. So bubble sort is adaptive, however, it is not stable. How can we make bubble sort adaptive?
>> Speaker 2: You said it is adaptive.
>> Bianca Gandolfo: It can be adaptive.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: Exit the main loop early if there are no swaps.
>> Bianca Gandolfo: Yep, exactly. So if we loop through our entire collection, or entire array. And we have no swaps, then we know that all of the greater elements are in their proper place. And so you can just break the loop early. And that would be a way to create an adaptive algorithm for bubble sort.
[00:03:07] Yeah, so you have a flag, right? True, false, something like that. Cool.
>> Speaker 4: Why isn't it stable though? It seems that we'd never swap equal things
>> Bianca Gandolfo: Why isn't it stable? Because, you couldn't swap equal things. Because the way that it swaps, it only swaps the adjacent ones.
[00:03:38] And it puts out of order automatically. Does that make sense? No.
>> Bianca Gandolfo: So let me think of a different way to say it. So,
>> Bianca Gandolfo: Hm.
>> Bianca Gandolfo: I wish I had a picture.
>> Speaker 4: Because the only way one thing can move past the other is if they're become adjacent.
[00:04:16] And then are swapped. And then you'd never swap them if they were equal.
>> Bianca Gandolfo: Yeah.
>> Speaker 4: It's a tangent and I don't want to
>> Bianca Gandolfo: Okay. No worries. So we'll just jump into insertion sort. So insertion sort is going to select the first element of an array. and then it's going to loop through the remainder of the array.
[00:04:45] Comparing it and either inserting it before or after. So can it be adaptive? Yes. Is it stable? Yes.
>> Bianca Gandolfo: Cool. Questions?
>> Bianca Gandolfo: Okay, moving on, selection sort. We are going to select the smallest one. We are going to put it into either a new array or at the beginning of the array.
[00:05:15] And keep selecting the next smallest element. It is not adaptive, it is not stable. We're good? Awesome. Reflection. What was your experience coding these out?
>> Speaker 5: The figures that you had, how do you think through was very helpful.
>> Bianca Gandolfo: The what?
>> Speaker 5: The figure.
>> Speaker 2: Animations?
>> Speaker 5: Animations, yes.
>> Bianca Gandolfo: Yeah, animations. We're hopeful we can figure out the order. I don't know if that's the best way of wording it. Cool.
>> Speaker 2: I kind of wish I had watched the other dances on my own time. Because I always think about that dance with the bubble sort. So I should have watched the others.
>> Bianca Gandolfo: Yeah, cool. Anything else? Anything that was harder than you were expecting?
>> Bianca Gandolfo: Easier than you expecting?
>> Bianca Gandolfo: No? It was about on target in terms of difficulty.
>> Speaker 6: I remember the insertion and selection being more difficult than the bubble to implement, but I don't remember specifically what I got from that.
[00:06:38] I just remember it took some effort.
>> Bianca Gandolfo: Cool. Anything else, anything that particularly helped you get to the exercises. Something like a mistake you made then fixed, a mistake that you still have that has not been fixed. [LAUGH] No. Okay.
>> Bianca Gandolfo: Okay.
>> Speaker 5: I like the way that she went through line by line and having the array first.
[00:07:12] And the items first and then switching and kind of. That was very helpful.
>> Bianca Gandolfo: Got it, so the more like visual, like a visual walkthrough of steps.
>> Speaker 5: Yeah
>> Bianca Gandolfo: Cool, awesome, cool. You guys ready? Further study non-comparison sorts, look these up they're kind of cool. Radix, Counting, Bucket