1
00:00:00,350 --> 00:00:01,850
- [Instructor] Insertion sort.

2
00:00:03,240 --> 00:00:06,870
Well, we've already seen
bubble sort and selection sort.

3
00:00:06,870 --> 00:00:08,040
Now we're going to take a look

4
00:00:08,040 --> 00:00:10,543
at another algorithm, insertion sort.

5
00:00:11,400 --> 00:00:13,550
Insertion sort works much the way

6
00:00:13,550 --> 00:00:17,630
you might sort cards in your
hand, when playing a card game.

7
00:00:17,630 --> 00:00:21,220
Imagine holding the cards in
your hand, fanning them out,

8
00:00:21,220 --> 00:00:24,520
and treating the leftmost card as sorted.

9
00:00:24,520 --> 00:00:27,250
Then, starting with the
next card to the right,

10
00:00:27,250 --> 00:00:29,440
you extract the card from your hand

11
00:00:29,440 --> 00:00:31,660
and insert it into the correct place,

12
00:00:31,660 --> 00:00:34,430
with respect to what's
already been sorted.

13
00:00:34,430 --> 00:00:35,863
That's insertion sort.

14
00:00:36,780 --> 00:00:39,640
Insertion sort is a stable algorithm

15
00:00:39,640 --> 00:00:42,080
and it tends to be a little
faster than bubble sort

16
00:00:42,080 --> 00:00:43,800
or selection sort.

17
00:00:43,800 --> 00:00:45,080
Why is that?

18
00:00:45,080 --> 00:00:46,670
It's because on each pass

19
00:00:46,670 --> 00:00:49,840
it ignores all but one unsorted element.

20
00:00:49,840 --> 00:00:51,620
And we're gonna have to look more closely

21
00:00:51,620 --> 00:00:53,123
to see why that works.

22
00:00:55,130 --> 00:00:57,020
Here's some pseudo-code.

23
00:00:57,020 --> 00:01:00,920
Notice that we start with
this index i equals one,

24
00:01:00,920 --> 00:01:05,430
because we're treating the
zeroth element as already sorted.

25
00:01:05,430 --> 00:01:10,210
And then, similar to bubble
sort and selection sort

26
00:01:10,210 --> 00:01:12,960
there is an outer loop and an inner loop.

27
00:01:12,960 --> 00:01:16,760
The outer loop iterates through
all elements in the vector.

28
00:01:16,760 --> 00:01:19,760
And for each element in the vector,

29
00:01:19,760 --> 00:01:24,760
we find a value of the
value that's at index i.

30
00:01:24,810 --> 00:01:27,930
Think of that as taking
the card out of your hand.

31
00:01:27,930 --> 00:01:31,980
And then for all the cards
that are to the left,

32
00:01:31,980 --> 00:01:34,500
see this is j equals i minus one,

33
00:01:34,500 --> 00:01:38,170
where j is the index of the inner loop,

34
00:01:38,170 --> 00:01:41,270
while j is greater than or equal to zero.

35
00:01:41,270 --> 00:01:46,070
And the value of v j is greater
than the value of the card

36
00:01:46,070 --> 00:01:50,650
that you're holding out, we
shift those cards to the right.

37
00:01:50,650 --> 00:01:53,600
This is the part that shifts
the cards to the right.

38
00:01:53,600 --> 00:01:57,480
And then we move to the left
to look at the next value.

39
00:01:57,480 --> 00:01:58,570
That's our while loop.

40
00:01:58,570 --> 00:02:01,810
So our while loop keeps
shifting cards to the right

41
00:02:01,810 --> 00:02:04,430
or values to the right in our vector,

42
00:02:04,430 --> 00:02:08,140
until we find a suitable
place to insert the element

43
00:02:08,140 --> 00:02:10,653
that we want to put into
its correct position.

44
00:02:11,530 --> 00:02:15,480
This pseudo-code here is saying

45
00:02:15,480 --> 00:02:17,410
this is where we insert the value.

46
00:02:17,410 --> 00:02:19,920
We've gone to the appropriate place

47
00:02:19,920 --> 00:02:22,230
and we've found a spot for it.

48
00:02:22,230 --> 00:02:27,230
And this iterates through all
of the elements in our vector,

49
00:02:27,340 --> 00:02:28,340
and then we're done.

50
00:02:29,410 --> 00:02:32,340
So let's make this a little more concrete.

51
00:02:32,340 --> 00:02:34,410
We'll use this example of cards.

52
00:02:34,410 --> 00:02:36,960
Here we have a vector of cards.

53
00:02:36,960 --> 00:02:40,660
We treat the leftmost card,
in this case the eight,

54
00:02:40,660 --> 00:02:42,140
as already sorted.

55
00:02:42,140 --> 00:02:44,920
And we begin our sorting with
the next card to the right,

56
00:02:44,920 --> 00:02:46,460
that's the three.

57
00:02:46,460 --> 00:02:49,960
Hence our pseudo-code
begins with an index one

58
00:02:49,960 --> 00:02:51,760
and not i equals zero.

59
00:02:51,760 --> 00:02:53,780
So we extract that card.

60
00:02:53,780 --> 00:02:56,740
We take it out of the vector.

61
00:02:56,740 --> 00:03:00,270
And then we're going to
shift all of the elements

62
00:03:00,270 --> 00:03:03,380
that are to the left of
that card, to the right,

63
00:03:03,380 --> 00:03:05,913
until we find a good
place to put that card.

64
00:03:06,820 --> 00:03:08,210
In this case it's simple.

65
00:03:08,210 --> 00:03:10,890
We only have to shift
the eight one position.

66
00:03:10,890 --> 00:03:12,640
This is the part that does the shifting,

67
00:03:12,640 --> 00:03:16,020
as shown in the pseudo-code earlier.

68
00:03:16,020 --> 00:03:18,660
And now you can see exactly
where that three's gonna go,

69
00:03:18,660 --> 00:03:21,770
it's gonna go to the left of the eight.

70
00:03:21,770 --> 00:03:24,200
And we insert it back into the vector

71
00:03:24,200 --> 00:03:26,290
in the appropriate position.

72
00:03:26,290 --> 00:03:27,540
That's insertion sort.

73
00:03:27,540 --> 00:03:30,563
In the next iteration
we'd pull the six out.

74
00:03:31,560 --> 00:03:33,770
We'd shift the eight over.

75
00:03:33,770 --> 00:03:35,610
We'd put the six in the correct place.

76
00:03:35,610 --> 00:03:36,970
We wouldn't need to shift the three,

77
00:03:36,970 --> 00:03:39,710
that would not be putting
it in the correct place.

78
00:03:39,710 --> 00:03:43,410
And we just iterate through
the whole vector that way.

79
00:03:43,410 --> 00:03:46,830
Notice that when we found
a spot for the three,

80
00:03:46,830 --> 00:03:50,210
we didn't have to look at
any of these other positions.

81
00:03:50,210 --> 00:03:53,163
We just completely ignored
this part of the vector.

82
00:03:54,050 --> 00:03:56,063
Let's take a look on VisuAlgo.

83
00:04:08,520 --> 00:04:10,680
The values that are already sorted

84
00:04:10,680 --> 00:04:13,113
are marked in that yellow or orange color.

85
00:04:15,550 --> 00:04:17,430
We pull the value out.

86
00:04:17,430 --> 00:04:20,450
We shift values over to the right

87
00:04:20,450 --> 00:04:23,963
until we find an appropriate
place to insert our value.

88
00:04:24,830 --> 00:04:26,033
And then we insert it.

89
00:04:27,170 --> 00:04:30,003
All those light blue elements,

90
00:04:31,090 --> 00:04:32,690
we're not even looking at those.

91
00:04:33,610 --> 00:04:35,333
Just completely ignore those.

92
00:04:40,500 --> 00:04:43,430
We only work within the
portion of the vector

93
00:04:43,430 --> 00:04:44,837
that's already sorted.

94
00:05:12,060 --> 00:05:14,473
So now we have a sorted list.

95
00:05:15,690 --> 00:05:20,040
Let's ask ourselves, is
insertion sort stable?

96
00:05:20,040 --> 00:05:21,330
Yes.

97
00:05:21,330 --> 00:05:22,463
Insertion sort guarantees

98
00:05:22,463 --> 00:05:25,040
that if duplicate values
appear in the vector,

99
00:05:25,040 --> 00:05:26,450
that their relative positions

100
00:05:26,450 --> 00:05:28,930
will be preserved after sorting.

101
00:05:28,930 --> 00:05:29,763
Now why is that?

102
00:05:29,763 --> 00:05:33,270
Let's go back to this
example of the cards.

103
00:05:33,270 --> 00:05:36,070
And here's a vector of cards
where we have duplicate values.

104
00:05:36,070 --> 00:05:37,790
Notice that we have two sixes,

105
00:05:37,790 --> 00:05:40,200
the six of clubs and the six of hearts.

106
00:05:40,200 --> 00:05:42,500
Notice also their relative positions.

107
00:05:42,500 --> 00:05:44,460
The six of clubs is on the left

108
00:05:44,460 --> 00:05:46,433
and the six of hearts is on the right.

109
00:05:47,980 --> 00:05:50,280
And we're gonna show that
that relative position

110
00:05:50,280 --> 00:05:52,053
is preserved during sorting.

111
00:05:52,970 --> 00:05:55,140
So that was our start vector.

112
00:05:55,140 --> 00:05:58,480
After three iterations our
vector will look like this,

113
00:05:58,480 --> 00:06:00,523
with six in the correct position.

114
00:06:02,830 --> 00:06:04,933
After five iterations,

115
00:06:05,780 --> 00:06:09,280
we have all of these
elements correctly sorted.

116
00:06:09,280 --> 00:06:12,270
And now we're ready to find
a place for that other six.

117
00:06:12,270 --> 00:06:15,870
So let's watch in detail what
happens in that iteration.

118
00:06:15,870 --> 00:06:18,710
We pull the six out of the vector.

119
00:06:18,710 --> 00:06:21,240
You can see that we're going
to shift the 10, the nine

120
00:06:21,240 --> 00:06:24,400
and the eight over one to the right,

121
00:06:24,400 --> 00:06:26,703
to make a space for the six.

122
00:06:28,880 --> 00:06:30,610
And then we're going to insert the six

123
00:06:30,610 --> 00:06:31,973
into the correct position.

124
00:06:33,070 --> 00:06:35,060
So we see that the relative positions

125
00:06:35,060 --> 00:06:37,250
of the two sixes is preserved.

126
00:06:37,250 --> 00:06:39,760
The six of clubs is still on the left

127
00:06:39,760 --> 00:06:41,870
and the six of hearts
is still on the right.

128
00:06:41,870 --> 00:06:44,343
So we know that insertion sort is stable.

129
00:06:47,090 --> 00:06:48,240
Now what about its complexity?

130
00:06:48,240 --> 00:06:50,120
Consider the worst case,

131
00:06:50,120 --> 00:06:52,310
where the input is
sorted in reverse order.

132
00:06:52,310 --> 00:06:55,060
It's not uncommon that
the worst case scenario

133
00:06:55,060 --> 00:06:58,940
is with the input in the
exactly the opposite order

134
00:06:58,940 --> 00:07:00,570
that you want it to be in.

135
00:07:00,570 --> 00:07:03,090
To put the last element
into the correct position

136
00:07:03,090 --> 00:07:05,980
we need to perform n minus one comparison

137
00:07:05,980 --> 00:07:07,900
and n minus one swaps.

138
00:07:07,900 --> 00:07:09,780
For the next element we need to perform

139
00:07:09,780 --> 00:07:14,630
n minus two comparisons and
n minus two swaps, and so on.

140
00:07:14,630 --> 00:07:19,300
And so this gives us
two times n minus one,

141
00:07:19,300 --> 00:07:22,640
plus n minus two, plus n
minus three, and so on,

142
00:07:22,640 --> 00:07:24,220
down to one.

143
00:07:24,220 --> 00:07:28,630
And if we solve that recurrence,
we get n times n minus one.

144
00:07:28,630 --> 00:07:33,143
And so we have a complexity
of big O of n squared.

145
00:07:34,130 --> 00:07:36,560
Here's a table showing a comparison

146
00:07:36,560 --> 00:07:39,070
of the three algorithms
we've looked at so far.

147
00:07:39,070 --> 00:07:41,993
Bubble sort, selection
sort and insertion sort.

148
00:07:43,210 --> 00:07:46,420
As we've said, insertion sort
is faster than bubble sort

149
00:07:46,420 --> 00:07:47,510
and selection sort,

150
00:07:47,510 --> 00:07:51,550
because it ignores the
unsorted portion of the vector.

151
00:07:51,550 --> 00:07:55,070
For the same reason, it
can process data online.

152
00:07:55,070 --> 00:07:56,240
What does that mean?

153
00:07:56,240 --> 00:07:59,550
Well, we have online
and offline algorithms.

154
00:07:59,550 --> 00:08:04,250
An online algorithm is one
that continues to take data

155
00:08:04,250 --> 00:08:05,563
while it's working.

156
00:08:06,650 --> 00:08:08,310
This means that while we're sorting,

157
00:08:08,310 --> 00:08:10,650
we could continue to add new elements

158
00:08:10,650 --> 00:08:13,710
to the unsorted portion of the vector,

159
00:08:13,710 --> 00:08:15,530
and the insertion sort algorithm

160
00:08:15,530 --> 00:08:18,020
would continue to work just fine.

161
00:08:18,020 --> 00:08:20,730
If we did this with bubble
sort or selection sort,

162
00:08:20,730 --> 00:08:22,323
these algorithms would fail.

163
00:08:23,160 --> 00:08:26,610
So one of the big differences
between insertion sort

164
00:08:26,610 --> 00:08:30,023
and these other two algorithms
is that it can work online.

165
00:08:31,140 --> 00:08:33,480
And despite the fact
that all the algorithms

166
00:08:33,480 --> 00:08:36,140
have O event squared complexity,

167
00:08:36,140 --> 00:08:38,870
insertion sort typically
outperforms bubble sort

168
00:08:38,870 --> 00:08:40,140
and selection sort.

169
00:08:40,140 --> 00:08:40,973
Why?

170
00:08:40,973 --> 00:08:44,300
For the exact reason that
I've already explained.

171
00:08:44,300 --> 00:08:48,520
Insertion sort only scans the
sorted portion of the vector

172
00:08:48,520 --> 00:08:51,900
when finding the correct
position for a given value.

173
00:08:51,900 --> 00:08:54,390
It limits the scope of its work.

174
00:08:54,390 --> 00:08:58,360
Furthermore, the closer
an out of place element is

175
00:08:58,360 --> 00:08:59,980
to its correct position,

176
00:08:59,980 --> 00:09:04,520
the fewer steps we need to put
it into the correct position.

177
00:09:04,520 --> 00:09:07,830
And that's another
feature of insertion sort

178
00:09:07,830 --> 00:09:09,320
that makes it a little faster

179
00:09:09,320 --> 00:09:11,533
than bubble sort and selection sort.

180
00:09:12,440 --> 00:09:15,020
So in summary, insertion sort has

181
00:09:15,020 --> 00:09:17,180
O event squared complexity.

182
00:09:17,180 --> 00:09:18,720
It's stable.

183
00:09:18,720 --> 00:09:22,460
It's generally faster than
bubble sort and selection sort.

184
00:09:22,460 --> 00:09:26,890
And in our next video, we're
gonna code it up in C++.

185
00:09:26,890 --> 00:09:30,030
We'll complete an implementation
of insertion sort.

186
00:09:30,030 --> 00:09:33,590
Also, we'll perform an
experiment where we set timers

187
00:09:33,590 --> 00:09:35,890
to time each of the three algorithms

188
00:09:35,890 --> 00:09:38,530
as they sort random vectors.

189
00:09:38,530 --> 00:09:41,490
It'll be interesting to see that result.

190
00:09:41,490 --> 00:09:42,440
That's all for now.