Original subtitles

1 1

(upbeat music) 2

2

(keyboard clicking) 3

3

Alright, the next algorithm 4

4

we're going to look at is Insertion Sort. 5

5

Like the other algorithms we've seen, 6

6

its partitions the array 7

7

into sorted and unsorted partitions. 8

8

But this time the implementation I'm going to show you, 9

9

grows assorted partition from left to right. 10

10

So it grows a sorted partition from the front of the array. 11

11

So how does Insertion Sort work? 12

12

Well, it starts out by saying that 13

13

the element position zero is in the sorted partition. 14

14

And because this sorted partition is of length one, 15

15

by default, the element is sorted. 16

16

Coz if you have an array of length one, 17

17

or a partition of length one, it's sorted, right? 18

18

There's only one element. 19

19

So at the beginning, the elements from position one 20

20

into the right or in the unsorted partition. 21

21

And so we're going to set 22

22

a first unsorted index field to one. 23

23

Now on each iteration, we take the first element 24

24

in the unsorted partition which will be the element 25

25

at array of first unsorted index, 26

26

and we insert it into the sorted partition. 27

27

And so at the end of each iteration 28

28

we will have grown this sorted partition by one. 29

29

And so what we'll do on the first iteration 30

30

is we will take 35, 31

31

because that's the first unsorted value. 32

32

And we will insert it into the sorted partition. 33

33

And at the end of the iteration, 34

34

the first two elements in the array will be sorted. 35

35

So how is each element inserted? 36

36

Well, what we do is we compare the value we're inserting 37

37

with the values in the sorted partition. 38

38

And we we traverse the sorted partition from right to left, 39

39

and we look for a value that is less than 40

40

or equal to the one we're trying to insert 41

41

because once we find that value, 42

42

we can stop looking we have found 43

43

the correct insertion position 44

44

for the new value that we're trying to insert. 45

45

Because remember, when we're inserting the value 46

46

we are working within the sorted partition. 47

47

And so if the element at index i in the sorted partition 48

48

is less than or equal to the element we're trying to insert, 49

49

then all of the values to the left of element i 50

50

will be less than or equal to the value 51

51

we're trying to insert, because all the values 52

52

are in sorted order. 53

53

So as we look for the correct insertion position, 54

54

we shift values in the sorted partition to the right. 55

55

And you'll see this in action right now. 56

56

Let's go through this by hand. 57

57

So on the first iteration, we're going to assign 35 58

58

to a new element field because 35 is the first element 59

59

in the unsorted partition. 60

60

And then we use i to traverse the sorted partition 61

61

from right to left. 62

62

So we compare 35 to 20. 63

63

Now 35 is greater than 20 so 35 is already 64

64

in its correct position in the sorted partition. 65

65

It's not in its correct position in the array, 66

66

but it is in the sorted partition. 67

67

So after the first iteration, disordered partition 68

68

has been grown to two lengths two 69

69

and the first two elements are in their correct position. 70

70

And now the first unsorted index is at index two 71

71

and i is assigned one, because that's the right most index 72

72

in the sorted partition. 73

73

So we assign -15 to new element. 74

74

And now we need to insert -15 into the sorted partition. 75

75

So we compare -15 against 35 ,-15 is less than 35. 76

76

And so we want to shift -15 down the array. 77

77

But another way of looking at it 78

78

is we're gonna shift 35 to the right 79

79

to make room for -15. 80

80

And so we we assign 35 to position two. 81

81

Now don't worry that might we've overwritten -15 82

82

because we haven't saved in a new element field. 83

83

So now we're going to compare -15 to 20, 84

84

15 is less than 20 so we're gonna shift 20 to the right 85

85

to make room for-15. 86

86

And at this point, we've hit the front of the array 87

87

so we have nothing else to compare -15 to 88

88

basically we have the smallest element 89

89

in the sorted partition and because we've hit the front 90

90

of the array, this is where we're going to insert -15. 91

91

And so we go ahead and do that. 92

92

And we've ended the second iteration. 93

93

And at this point, we've grown 94

94

the sorted partition to three. 95

95

And the first three elements in the array, 96

96

which is a sorted partition are in their correct positions 97

97

in the sorted partition. 98

98

So now the first unsorted indexes at position three. 99

99

So we're going to going to assign the value of seven 100

100

to new element and we're going to compare seven against 35. 101

101

Seven is less than 35. 102

102

So we're gonna shift 35 to the right. 103

103

We compare seven against 20, seven is less than 20. 104

104

So we're gonna shift 20 to the right 105

105

and then we compare seven against -15. 106

106

Seven is greater than -15. 107

107

So we have found the insertion position. 108

108

Remember, we're working within the sorted partition. 109

109

So if there was anything to the left of -15, 110

110

all those values would be less than -15. 111

111

So there's no need to keep traversing the sorted partition 112

112

the moment we have hit an element 113

113

that's less than or equal to the one we're trying to insert, 114

114

we found that correct insertion position. 115

115

And so we're going to insert seven into position one. 116

116

And we have completed another iteration, 117

117

we've grown the sorted partition by one. 118

118

And all of the elements in the sorted partition are sorted. 119

119

So the next element we're going 120

120

to want to insert is 55. 121

121

So we compare 55 against 35, 55 is greater than 35. 122

122

So we've already found it's correct position. 123

123

And so we completed this iteration. 124

124

And now the first five elements in the array 125

125

are their correct sorted position. 126

126

Now, I'm not going to go through one and -22, 127

127

because one is gonna get shifted 128

128

all the way down to position one, 129

129

and then -22 will be shifted all the way 130

130

down to position zero. 131

131

So I won't bore you with slides doing that. 132

132

I think you at this point, 133

133

you get the gist of the algorithm. 134

134

And so that's Insertion Sort. 135

135

It starts out by saying the first element is sorted. 136

136

The implementation or at least the implementation 137

137

that I'm going to show you does that. 138

138

It grows the sorted partition from left to right. 139

139

And on each iteration, it picks off the first element 140

140

in the unsorted partition and it inserts it 141

141

into the correct position in the sorted partition. 142

142

And it does that by shifting elements to the right 143

143

to make room for the new element. 144

144

So Insertion Sort is an In-place algorithm. 145

145

We don't need to create any temporary arrays, 146

146

we have a few extra fields. 147

147

But as I've said before, 148

148

as long as the extra memory we're using 149

149

doesn't depend on the number of items were sorted. 150

150

It's an In-place algorithm. 151

151

It's a quadratic algorithm. 152

152

And it's a stable algorithm. 153

153

It's stable because when we're picking off elements, 154

154

we're doing that from left to right. 155

155

So if let's say there are two nines in the array, 156

156

we're going to insert the left most nine first 157

157

and then when we come to the right most nine. 158

158

Remember that when we're looking for the insertion position, 159

159

we stop when we hit an element that is less than or equal 160

160

to the one that we're inserting. 161

161

So when we're inserting the nine, 162

162

we're eventually going to hit the first nine, 163

163

we inserted into the sorted partition. 164

164

And that second nine will be inserted 165

165

to the right of the first nine. 166

166

And so the relative positions 167

167

of those two nines will be preserved. 168

168

And so insertion sort is a stable sort algorithm. 169

169

Okay, so that's an explanation of Insertion Sort. 170

170

And we've gone through the implementation 171

171

I'm going to show you, 172

172

so let's get on to coding that implementation. 173

173

I'll see you in the next video.