Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic trial
to watch this video
Now we're going to look at an algorithm named Selection Sort. It's still slow, but at least each pass through the list brings it a little closer to completion.
Again, see the instruction step following this video for code to implement this algorithm in various languages!
Previously, we showed you Bogosort, a terrible sorting algorithm that basically randomizes the order of a list and then checks to see if it happens to be sorted. The problem with Bogosort is that it doesn't get any closer to a solution with each operation, and so with lists that have more than a few items, it will probably never finish sorting them.
Now we're going to look at an algorithm named Selection Sort. It's still slow, but at least each pass through the list brings it a little closer to completion.
Our implementation of selection sort is going to use two arrays, an unsorted array and a sorted one. (Some versions move values around within just one array, but we're using two arrays to keep the code simpler.) The sorted list starts out empty, but we'll be moving values from the unsorted list to the sorted list one at a time. With each pass, we'll look through each of the values in the unsorted array, find the smallest one, and move that to the end of the sorted array.
Suppose our unsorted list looks like this:
[8, 5, 1, 4, 7]
We'll start with the first value in the unsorted array, and say that's the "minimum", or smallest, value we've seen so far. Then we'll look at the next value and see if that's smaller than the current minimum. If it is, we'll mark that as the new minimum. Then we'll move to the next value and compare that to the minimum again. If it's smaller, that becomes the new minimum. We continue that way until we reach the end of the list. At that point, we know whatever value we have marked as the minimum is the smallest value in the whole list.
Now, here's the part that makes selection sort better than Bogosort: we then move that minimum value from the unsorted list to end of the sorted list. The minimum value isn't part of the unsorted list anymore, so we don't have to waste time looking at it any more. All our remaining comparisons will be on the remaining values in the unsorted list.
Then we start the process over. At this point, our list consists of the numbers [8, 5, 4, 7]
. Our first minimum is 8. We start by comparing the minimum to 5. 5 is smaller than 8, so 5 becomes the new minimum. Then we compare 5 to 4, and 4 becomes the new minimum. 4 is not smaller than 7, though, so 4 remains the minimum. 4 gets moved to the end of the sorted array, becoming its second element.
The process repeats again: 8 is the first minimum, but 5 is smaller so that becomes the new minimum. 7 is larger so 5 stays as the minimum, and 5 is what gets moved over to the sorted array.
And so on, until there are no more items left in the unsorted array, and all we have left is the sorted array.
The movement of numbers from "unsorted" to "sorted" will look like this.
Unsorted Sorted
[8, 5, 1, 4, 7] []
[8, 5, 4, 7] [1]
[8, 5, 7] [1, 4]
[8, 7] [1, 4, 5]
[8] [1, 4, 5, 7]
[] [1, 4, 5, 7, 8]

0:00
Previously we showed you bogo_sort, a terrible sorting algorithm that basically

0:04
randomizes the order of the list and then checks to see if it happens to be sorted.

0:09
The problem with bogo_sort is that is doesn't get any closer to

0:12
a solution with each operation.

0:14
And so with lists that have more than a few items,

0:17
it will probably never finish sorting them.

0:20
Now we're going to look at an algorithm named selection_sort.

0:23
It's still slow but

0:24
at least each pass through the list brings it a little closer to completion.

0:29
Our implementation of selection_sort is going to give two arrays,

0:33
an unsorted array and sorted one.

0:36
Some version move values around within just one array, but

0:39
we're using two arrays to keep the code simpler.

0:42
The sorted list starts out empty, but

0:44
we'll be moving values from the unsorted list to the sorted list one at a time.

0:48
With each pass we'll look through each of the values in the unsorted array,

0:52
find the smallest one, and move that to the end of the sorted array.

0:56
We'll start with the first value in the unsorted array and

1:00
say that's the minimum or smallest value we've seen so far.

1:03
Then we'll look at the next value and

1:05
see if that's smaller than the current minimum.

1:07
If it is we'll mark that as the new minimum.

1:10
Then we'll move to the next value and compare that to the minimum again.

1:14
If it's smaller, that becomes the new minimum.

1:16
We continue that way until we reach the end of the list.

1:19
At that point we know whatever value we have marked as the minimum is the smallest

1:24
value in the whole list.

1:25
Now, here's the part that makes selection_sort better than bogo_sort.

1:30
We then move that minimum value from the unsorted list to the end of

1:33
the sorted list.

1:34
The minimum value isn't part of the unsorted list anymore, so

1:38
we don't have to waste time looking at it anymore.

1:41
All our remaining comparisons will be on the remaining values in the unsorted list,

1:46
then we start the process over.

1:48
At this point our list consists of the numbers eight, five, four, and seven.

1:52
Our first minimum is eight.

1:54
We start by comparing the minimum to five.

1:57
Five is smaller than eight, so five becomes the new minimum.

2:00
Then we compare five to four, and four becomes the new minimum.

2:04
Four is not smaller than seven though, so four remains the minimum.

2:08
Four gets moved to the end of the sorted array, becoming its second element.

2:13
The process repeats again.

2:13
Eight is first minimum, but five is smaller so that becomes the minimum.

2:18
Seven is larger, so five stays as the minimum.

2:21
And five is what gets moved over to the sorted array.

2:24
And so on until there are no more items left in the unsorted array and

2:27
all we have left is the sorted array.

2:30
So that's how selection sort works in general,

2:33
now let's do an actual implementation of it.

2:36
This code here at the top is the same as we saw in the bogo_sort example.

2:40
It just loads a Python list of numbers from a file.

2:44
Let's implement the function that will do our selection sort.

2:47
We're going to pass in our Python list containing all the unsorted numbers.

2:52
We'll create an empty list that will hold all our sorted values.

2:57
We'll loop once for each value in the list.

3:01
We call a function named index_of_min, which we're going to write in just

3:05
a minute, that finds the minimum value in the unsorted list and returns its index.

3:10
Then we call the pop method on the list, and

3:12
pass it the index of the minimum value.

3:14
Pop will remove that item from the list and return it.

3:17
We then add that value to the end of the sorted list.

3:21
Going up a level of indentation signals to Python that we're ending the loop.

3:26
After the loop finishes, we return the sorted list.

3:30
Now we need to write the function that picks out the minimum value.

3:34
We pass in the list we're going to search.

3:36
We mark the first value in the list as the minimum.

3:39
It may or may not be the actual minimum, but

3:41
it's the smallest we've seen on this pass through the list.

3:45
It's also the only value we've seen on this pass through the list so far.

3:49
Now we loop through the remaining values in the list after the first.

3:53
We test whether the value we're currently looking at is less than the previously

3:58
recorded minimum.

4:01
If it is, then we set the current index as the new index of the minimum value.

4:06
After we've looped through all the values,

4:08
we return the index of the smallest value we found.

4:11
Lastly, we need to actually run our selection_sort method and

4:15
print the sorted list it returns.

4:17
Let's save this, and now let's try running it.

4:20
We run the Python command and pass at the name of our script, selection_sort.py.

4:25
In the numbers directory I've saved several data files filled with random

4:30
numbers, one on each line.

4:31
5.txt has 5 lines, 8.txt has 8 lines, and

4:34
to help us really measure the speed of our algorithms, 10000.txt has 10,000 lines.

4:40
I've even created a file with a million numbers.

4:43
Our script takes the path of a file to load as an argument.

4:46
So I'll give it the path of our file with five numbers, numbers/5.txt.

4:53
The script runs, reads the numbers in the file into a list,

4:56
calls our selection_sort method with that list, and then prints the sorted list.

5:01
Let me add a couple print statements within the selection_sort function so

5:04
you can watch the sort happening.

5:07
Don't worry about figuring out the Python formatting string that I use,

5:10
it's just there to keep the two lists neatly aligned.

5:13
I'll add the first print statement before the loop runs at all.

5:21
I'll have it print out the unsorted list and the sorted list.

5:24
I'll add an identical print statement within the loop so

5:28
we can watch values moving from the unsorted list to the sorted list.

5:33
Let's save this.

5:36
And we'll try running the same command again.

5:38
The output looks like this.

5:40
You can see the unsorted list on the left and the sorted list on the right.

5:45
Initially the sorted list is empty.

5:48
On the first pass it selects the lowest number, one, and

5:51
moves it to the sorted list.

5:53
Then it moves the next lowest number over, four.

5:56
This repeats until all the numbers have been moved to the sorted list.

6:00
I have another file with eight different numbers in it.

6:03
Let's try our program with that.

6:04
Python selection_sort.py numbers/8.txt.

6:13
You can see the same process at work here.

6:15
Notice that this file had some duplicate values too.

6:18
That's okay though because the index of min function only updates

6:22
the minimum index if the current value is less than the previous minimum.

6:26
If they're equal it just keeps the first minimum value it found, and

6:30
waits to move the duplicate value over until the next pass through the list.
You need to sign up for Treehouse in order to download course files.
Sign up