1
00:00:01,160 --> 00:00:02,560
- [Narrator] Selection sort.
2
00:00:03,860 --> 00:00:07,610
In the previous two
videos, we saw bubble sort.
3
00:00:07,610 --> 00:00:09,830
Selection sort is another algorithm
4
00:00:09,830 --> 00:00:12,870
that works by swapping
elements in a vector.
5
00:00:12,870 --> 00:00:14,420
Selection sort is designed
6
00:00:14,420 --> 00:00:17,180
to make the fewest swaps possible.
7
00:00:17,180 --> 00:00:18,930
So for a vector of n elements,
8
00:00:18,930 --> 00:00:21,433
selection sort will make n swaps.
9
00:00:23,910 --> 00:00:26,700
Taking a few liberties,
we can write pseudo code
10
00:00:26,700 --> 00:00:29,380
for this algorithm in two lines.
11
00:00:29,380 --> 00:00:31,600
While this is a little too concise,
12
00:00:31,600 --> 00:00:34,660
it shows how simple the idea is.
13
00:00:34,660 --> 00:00:37,490
We iterate through a vector n times,
14
00:00:37,490 --> 00:00:40,900
and at each iteration we
swap the element at index i
15
00:00:40,900 --> 00:00:42,770
with the minimum element found
16
00:00:42,770 --> 00:00:46,083
between indices i and n minus one.
17
00:00:47,280 --> 00:00:48,590
Notice that this implies
18
00:00:48,590 --> 00:00:51,620
a division of the vector into two parts.
19
00:00:51,620 --> 00:00:54,450
The part with indices less than i,
20
00:00:54,450 --> 00:00:56,960
that's the part that's
already been sorted,
21
00:00:56,960 --> 00:01:00,600
and the indices greater
than or equal to i,
22
00:01:00,600 --> 00:01:02,563
that's the part we have yet to sort.
23
00:01:03,560 --> 00:01:06,603
So let's expand on this
pseudo code just a bit.
24
00:01:08,740 --> 00:01:10,460
Here's the expanded pseudo code
25
00:01:10,460 --> 00:01:12,620
to show that there is an inner loop,
26
00:01:12,620 --> 00:01:15,080
one that scans the unsorted values
27
00:01:15,080 --> 00:01:17,493
to find the minimum unsorted value.
28
00:01:18,420 --> 00:01:21,170
Again, the vector is
divided into two parts,
29
00:01:21,170 --> 00:01:23,000
the part that's already sorted,
30
00:01:23,000 --> 00:01:25,560
and the part we have yet to sort.
31
00:01:25,560 --> 00:01:27,900
It is this latter part that gets processed
32
00:01:27,900 --> 00:01:28,800
in the inner loop.
33
00:01:30,020 --> 00:01:33,280
So in that inner loop,
we just update the index
34
00:01:33,280 --> 00:01:36,543
of the minimum value when
we find a smaller value.
35
00:01:38,810 --> 00:01:40,090
And when that's done,
36
00:01:40,090 --> 00:01:42,793
and we've found a minimum
value, we perform the swap.
37
00:01:44,000 --> 00:01:45,700
Let's look at this with a diagram.
38
00:01:47,880 --> 00:01:49,220
Here we have a vector,
39
00:01:49,220 --> 00:01:51,920
and everything to the left
of the arrow is sorted.
40
00:01:51,920 --> 00:01:54,380
You'll notice there's nothing
to the left of the arrow,
41
00:01:54,380 --> 00:01:56,233
so we start with nothing sorted.
42
00:01:57,630 --> 00:02:00,180
Then we scan through the list,
43
00:02:00,180 --> 00:02:01,760
and we find the minimum element
44
00:02:01,760 --> 00:02:04,640
in the portion of the vector
to the right of the arrow.
45
00:02:04,640 --> 00:02:08,050
And then we swap it with the
leftmost unsorted element.
46
00:02:08,050 --> 00:02:10,233
Here we swap zero with seven.
47
00:02:12,930 --> 00:02:15,543
Now the first element
in the list is sorted.
48
00:02:17,590 --> 00:02:19,300
And then we perform the same steps
49
00:02:19,300 --> 00:02:20,883
on the balance of the list.
50
00:02:22,470 --> 00:02:25,570
We find the minimum value
in the unsorted portion,
51
00:02:25,570 --> 00:02:28,760
here it's one, and we swap it
52
00:02:28,760 --> 00:02:31,310
with the left most unsorted element.
53
00:02:31,310 --> 00:02:34,283
We just repeat this process
until the list is sorted.
54
00:02:35,380 --> 00:02:38,793
Let's watch a demonstration
on the Visualgo website.
55
00:02:46,450 --> 00:02:48,363
Here we have a little larger vector,
56
00:02:52,420 --> 00:02:55,073
but I've set the speed
to move pretty quickly.
57
00:02:56,860 --> 00:03:00,500
You'll see that sorted elements,
58
00:03:00,500 --> 00:03:03,513
elements that are already
sorted are colored orange.
59
00:03:06,720 --> 00:03:10,300
The minimum that's been found,
60
00:03:10,300 --> 00:03:12,850
and the element it's swapped
with or marked in red,
61
00:03:18,530 --> 00:03:20,190
and the element that's being scanned
62
00:03:20,190 --> 00:03:21,863
at the moment is in green.
63
00:03:34,400 --> 00:03:37,350
Now, you'll see 36 doesn't
change position there
64
00:03:37,350 --> 00:03:39,783
because it was already
in the correct position.
65
00:03:44,000 --> 00:03:46,873
Again, 46 here won't change position.
66
00:03:48,900 --> 00:03:50,623
And now we have a sorted list.
67
00:03:51,990 --> 00:03:54,360
Is selection sort stable?
68
00:03:54,360 --> 00:03:58,020
No, selection sort does not guarantee
69
00:03:58,020 --> 00:04:00,330
that if duplicate values
appear on the vector,
70
00:04:00,330 --> 00:04:01,960
that their relative positions
71
00:04:01,960 --> 00:04:03,833
will be preserved after sorting.
72
00:04:04,840 --> 00:04:06,100
Why is this?
73
00:04:06,100 --> 00:04:09,780
Well, let's consider the
vector three, five, six,
74
00:04:09,780 --> 00:04:12,050
seven, three, one.
75
00:04:12,050 --> 00:04:14,980
We have two threes, so
we have duplicate values.
76
00:04:14,980 --> 00:04:16,490
But after the first pass,
77
00:04:16,490 --> 00:04:18,900
the three that was in
the left-most position
78
00:04:18,900 --> 00:04:21,230
will be swapped with the value one,
79
00:04:21,230 --> 00:04:23,120
the far right-hand side of the vector,
80
00:04:23,120 --> 00:04:27,310
and this changes the relative
position of the two threes.
81
00:04:27,310 --> 00:04:29,710
Yes, it's true that the next two passes
82
00:04:29,710 --> 00:04:30,910
will move the two threes
83
00:04:30,910 --> 00:04:33,540
to the second and third
positions in the vector,
84
00:04:33,540 --> 00:04:34,760
and that that operation
85
00:04:34,760 --> 00:04:37,110
will preserve their relative positions,
86
00:04:37,110 --> 00:04:38,660
but their relative positions
87
00:04:38,660 --> 00:04:41,330
were already changed in the first step,
88
00:04:41,330 --> 00:04:43,823
so selection sort is not stable.
89
00:04:45,710 --> 00:04:48,120
What about its time complexity?
90
00:04:48,120 --> 00:04:51,860
Well, we have an inner
loop and an outer loop,
91
00:04:51,860 --> 00:04:55,400
and selection sort makes n
passes through the vector,
92
00:04:55,400 --> 00:04:59,500
and in the ith pass, it
performs n minus i comparisons,
93
00:04:59,500 --> 00:05:01,790
so the complexity analysis is similar
94
00:05:01,790 --> 00:05:03,740
to that of bubble sort.
95
00:05:03,740 --> 00:05:08,740
We have a sequence of terms
that goes from n down to one.
96
00:05:09,210 --> 00:05:12,830
And if we simplify that we get
n squared minus n over two,
97
00:05:12,830 --> 00:05:16,420
so the complexity is O of n squared.
98
00:05:16,420 --> 00:05:17,963
Let's do a quick comparison.
99
00:05:18,840 --> 00:05:22,050
Here's a comparison of
selection sort and bubble sort.
100
00:05:22,050 --> 00:05:25,490
We see they both have time
complexity events squared,
101
00:05:25,490 --> 00:05:29,070
they both have constant space complexity,
102
00:05:29,070 --> 00:05:32,263
bubble sort is stable while
selection sort is not,
103
00:05:33,840 --> 00:05:36,920
bubble sort can tell if
the list is already sorted.
104
00:05:36,920 --> 00:05:40,020
So, the one thing bubble
sort has going for it
105
00:05:40,020 --> 00:05:43,020
is that if you give it
an already sorted list,
106
00:05:43,020 --> 00:05:45,003
it will terminate almost immediately,
107
00:05:45,930 --> 00:05:48,843
but selection sort
performs the fewest swaps.
108
00:05:49,770 --> 00:05:51,350
Now, how did we get that value
109
00:05:51,350 --> 00:05:53,670
for constant space complexity?
110
00:05:53,670 --> 00:05:55,290
We considered the extra memory
111
00:05:55,290 --> 00:05:57,123
needed to implement the algorithm.
112
00:05:58,280 --> 00:05:59,900
Bubble sort and selection sort
113
00:05:59,900 --> 00:06:03,080
both require a temporary
variable for swapping,
114
00:06:03,080 --> 00:06:05,800
and selection sort also
requires a variable
115
00:06:05,800 --> 00:06:09,610
representing the current
minimum found so far.
116
00:06:09,610 --> 00:06:11,780
But in both cases, this is constant
117
00:06:11,780 --> 00:06:14,840
and does not vary with
the size of the input.
118
00:06:14,840 --> 00:06:18,410
Hence their space
complexities are big O of one.
119
00:06:18,410 --> 00:06:21,080
Now, a little comprehension check.
120
00:06:21,080 --> 00:06:22,890
Given this vector of integers,
121
00:06:22,890 --> 00:06:25,210
zero, one, six, five, three, nine,
122
00:06:25,210 --> 00:06:27,250
two, four, seven, eight,
123
00:06:27,250 --> 00:06:28,830
what will the vector look like
124
00:06:28,830 --> 00:06:31,720
after one pass of bubble sort?
125
00:06:31,720 --> 00:06:33,823
How many swaps will take place?
126
00:06:35,810 --> 00:06:38,850
Well, we're gonna swap six with five
127
00:06:38,850 --> 00:06:41,190
and then six is gonna be next to three
128
00:06:41,190 --> 00:06:43,690
and we'll swap six with three,
129
00:06:43,690 --> 00:06:46,740
six and nine are gonna
be in the correct order.
130
00:06:46,740 --> 00:06:49,240
So now we're gonna swap nine with two,
131
00:06:49,240 --> 00:06:51,880
nine with four, nine with seven,
132
00:06:51,880 --> 00:06:54,450
nine with eight, that's six swaps.
133
00:06:54,450 --> 00:06:56,300
And so our vector will look like
134
00:06:56,300 --> 00:06:58,730
zero, one, five, three, six, two,
135
00:06:58,730 --> 00:07:00,860
four, seven, eight, nine.
136
00:07:00,860 --> 00:07:03,600
What will it look like
with selection sort,
137
00:07:03,600 --> 00:07:05,900
given that zero and one are already sorted
138
00:07:05,900 --> 00:07:07,530
and in the correct positions.
139
00:07:07,530 --> 00:07:10,320
What will the vector
look like after one pass?
140
00:07:10,320 --> 00:07:12,760
And how many swaps will take place?
141
00:07:12,760 --> 00:07:14,590
Well, it's selection sort,
142
00:07:14,590 --> 00:07:17,310
so we know we're only going
to swap once per pass,
143
00:07:17,310 --> 00:07:20,220
so there's only going to be one swap.
144
00:07:20,220 --> 00:07:22,940
And we're gonna swap the minimum value
145
00:07:22,940 --> 00:07:26,530
that we find in the unsorted
portion of the vector
146
00:07:26,530 --> 00:07:29,750
with the left most unsorted value.
147
00:07:29,750 --> 00:07:31,690
So we're gonna swap two and six.
148
00:07:31,690 --> 00:07:33,100
And so we'll get the vector
149
00:07:33,100 --> 00:07:35,970
zero, one, two, five, three, nine,
150
00:07:35,970 --> 00:07:38,763
six, four, seven and eight with one swap.
151
00:07:41,150 --> 00:07:43,500
Now let's return to our
comparison with bubble sort
152
00:07:43,500 --> 00:07:44,483
for another moment.
153
00:07:45,550 --> 00:07:49,550
Despite both algorithms having
O of n squared complexity,
154
00:07:49,550 --> 00:07:53,500
selection sort typically
outperforms bubble sort.
155
00:07:53,500 --> 00:07:54,540
Why is that?
156
00:07:54,540 --> 00:07:57,550
Well, changing the value
of a variable and memory,
157
00:07:57,550 --> 00:08:01,210
that is writing to the
variable is more expensive,
158
00:08:01,210 --> 00:08:05,220
it takes a longer time
than reading the value.
159
00:08:05,220 --> 00:08:07,410
And selection sort is designed
160
00:08:07,410 --> 00:08:10,030
to make the fewest swaps possible.
161
00:08:10,030 --> 00:08:15,030
Therefore it performs fewer
rights than bubble sort does,
162
00:08:15,030 --> 00:08:17,230
hence it tends to be faster.
163
00:08:17,230 --> 00:08:19,660
We're going to investigate
this in greater depth
164
00:08:19,660 --> 00:08:21,373
when we get to project four.
165
00:08:22,370 --> 00:08:27,240
So in summary, selection sort
has O of n squared complexity,
166
00:08:27,240 --> 00:08:29,110
it's not stable,
167
00:08:29,110 --> 00:08:33,250
it's designed to perform
the fewest swaps possible.
168
00:08:33,250 --> 00:08:36,830
And again, I encourage
you to visit visualgo.net
169
00:08:36,830 --> 00:08:38,233
to try it out on your own.
170
00:08:39,550 --> 00:08:42,330
In the next video, we'll code up a version
171
00:08:42,330 --> 00:08:46,310
of selection sort in C++,
but that's all for now.
172
00:08:46,310 --> 00:08:47,143
Thanks.