Name: 0.3 Data Structures & Algorithms: Selection Sort
Uploaded: 2025-01-06T13:33:15.000Z
Duration: 7 min 5 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Okay, so let's talk about this idea of sorting integers.

So, I'm going to look at a specific example problem.

So, we're going to look at sorting a couple of different numbers, and then we'll kind of build off of this idea and look at sorting more data.

Okay, so for our simple problem, we've got the numbers 89, 3, and 1.

So we could come up with some sort of an algorithm to try and sort these.

So, one of the simplest things we could do is we could just try all possible combinations until we find one that's sorted.

So basically, we could go through every possible ordering of these until we identify one that's clearly sorted.

So I could start with whatever order I was initially given, and then I could swap two elements.

And eventually, we'll stumble across the perfectly sorted order.

Of course, obviously, this seems very, very, very inefficient.

With just a simple problem like this, it was probably obvious to you what the order should have been when you just first glanced at it.

The human brain is incredible at pattern matching.

But for the rest of our discussion here, we'll want to think very, very concretely and think about each individual step so we could translate it into code rather than relying on our instantaneous intuition about what the problem should be.

Okay, our first sorting algorithm seems a little bit cumbersome.

So let's add in some more data here, and we'll talk about a second type of sorting algorithm.

So now we're going to take a look at what's called a selection sort.

So a selection sort is called a selection sort because a lot of the work takes place in selecting a value.

So the way a selection sort works is it's going to try and select the value that belongs in our next available position.

So by that, I mean we'll start off trying to find the value that belongs in the very beginning of the array.

Once we've found the value that belongs in the beginning of the array, we'll move on and we'll try and find the value that belongs in the second position of the array.

After we've done that, we'll try and find the value that belongs in the third position of the array.

So let's go back and talk about that first step.

We want to know what belongs in the first position of the array.

The thing that belongs in the very first position will end up being the smallest number overall, the minimum value.

So let's think about the steps that a computer program is going to have to go through in order to find the minimum value.

Now, when we see this visually, our brain is so good that it just instantly looks at the values and identifies the first one.

But remember that a computer program isn't visual.

It's looking at an individual box and then somehow comparing it and contrasting it with others.

So when our program first looks at this box, it has nothing to compare it to.

That might be the thing that belongs in the beginning of this array.

So I'm going to use my pencil here to keep track of which item I'm evaluating.

And I'm going to indicate the one that seems like my candidate for the best possible value by slightly offsetting it.

So when we get to 34, that's no better than 2.

And I'm going to continue on, even though we know visually that 1 is our best value.

Remember, the computer is processing step by step.

There could be a negative number out here or a 0.

So I get to 3, no better than 1. 89, no better than 1. 13, no better than 1. 55, no better than 1.

So I've gone all the way through my data and I've found the minimum value overall.

And I know that that belongs in the very first position of my array.

Not only that, I'm going to kind of set this off to the side and kind of ignore it.

I know that that belongs in the very first position of my array.

Oh, at this point, I can repeat the process starting from the second position.

So I've already removed the overall minimum value and kind of set it off to the side.

Now if I process the remainder of my array in the exact same way and find the minimum value of what's remaining, that's going to be my second minimum value and belong in the second position of the array.

So let's go through this exercise a few more times. 34 seems pretty good when I first look at it, but then I move on to 2 and that's much better. 3 is no better than 2. 89 is no better than 2. 13 is no better than 2. 55 is no better than 2.

So we get to the end and now we know that 2 belongs in that second position.

And again, I'm leaving a little gap here so I can kind of tell where my unsorted data begins and where my sorted data is at.

Now I'm at the third position of the array.

I've removed the minimum overall and the second minimum.

So let's go through the process again. 34 seems pretty good until I see 3. 89, 13, and 55.

Now I've got fully sorted data for 3 items and then I've got my unsorted set.

That's okay. 89, oh, 13 is better than my 34. 55 is no better.

Swap my minimum value with my first value.

Repeat the process. 89 seems pretty good until I happen to stumble across the 34. 55 is no better than 34.

I have my sorted set and my unsorted set. 89 seems pretty good until I see 55.

My unsorted set only has one number so we'll just go ahead and add that on.

At this point I'm done and it's completely sorted.

So remember that I was doing the bulk of the work in this process of selecting the next item, which is why this is called selection sort.

Okay, of course, this process isn't limited to just numbers.

We could also use this idea of selection sort with words or anything else that we can construct a total ordering out of.

So these are the surnames of some relatively famous computer scientists.

So starting with Hopper seems like a good candidate for a first overall.

Turing's no earlier in the alphabet than Hopper.

Then we get to Corman, and Corman doesn't come any earlier than Allen, so Allen goes to the front.

Hopper gets swapped back to where Allen was just at.

Turing seems pretty good until we see Rivest.

 Okay, anyway, so the basic idea is that we can even do this sorting process with other types of data, not just with integers, so it does generalize.