Original subtitles

1 1

(bright music) 2

2

(keyboard clacking) 3

3

All right, so let's implement insertion sort. 4

4

I've already created the project. 5

5

I'll be putting code into 6

6

academy.learnprogramming.insertionsort. 7

7

I've added the usual array and code to print the array. 8

8

And this implementation doesn't need the swap method. 9

9

We don't swap, we shift elements. 10

10

And so I have not added the swap method 11

11

because we don't need it. 12

12

Okay, so let's get going, 13

13

so we'll say for int firstUnsortedIndex 14

14

equals one 15

15

because remember, this implementation starts out 16

16

by assuming that the element at position zero 17

17

is in the sorted partition, 18

18

and so the first unsorted index will start at one. 19

19

And then we're gonna keep going 20

20

as long as the first unsorted index 21

21

is less than the length of the array. 22

22

So we're gonna examine all the elements 23

23

right up to the end of the array. 24

24

And after each iteration, 25

25

the first unsorted index will be incremented by one, 26

26

because we're growing the sorted partition 27

27

from left to right, and so the first unsorted index 28

28

is going to be increasing by one after every iteration. 29

29

Okay, so the first thing we're gonna do 30

30

is save the value of the element we're going to insert 31

31

into new element 32

32

because as you saw in the slides, when we do the shifting, 33

33

that position, the element, is going to be overwritten. 34

34

And so we need to save the value off, 35

35

so we're gonna save off intArray firstUnsortedIndex 36

36

and I'm going to declare i outside the loop 37

37

because I need it after the loop. 38

38

And now, we're going to code the loop 39

39

that does the traversal of the sorted partition 40

40

and looks for the correct position to insert new element. 41

41

So we're gonna say for i equals firstUnsortedIndex 42

42

because when we start out, the element we want to insert 43

43

is that first inserted index, 44

44

and we're going to continue to loop, 45

45

in other words, we're going to continue to look 46

46

and keep shifting items, as long as i is greater than zero 47

47

because that means we haven't hit the front of the array. 48

48

And... 49

49

And we'll keep going as long as 50

50

whatever's at intArray i minus one 51

51

is greater than newElement. 52

52

So what is this doing? 53

53

Just to go over this again, 54

54

we want to keep looking for the insertion position 55

55

as long as we haven't hit the front of the array 56

56

because if we hit the front of the array, 57

57

it means that the element we're trying to insert 58

58

is the smallest element we've seen so far 59

59

and the correct insertion position is zero. 60

60

And we wanna keep looking as long as 61

61

the element we're looking at in the sorted partition 62

62

is greater than the one we're trying to insert, 63

63

because if the element at i minus one is greater 64

64

than the element we're trying to insert, 65

65

then we still haven't found the correct insertion position. 66

66

So the moment we hit the front of the array, 67

67

or the moment we hit an element that is less than 68

68

or equal to the element we're trying to insert, 69

69

we have found the correct insertion position. 70

70

And on each iteration, we're going to decrement i 71

71

because remember we are traversing the sorted partition 72

72

and doing the comparisons from right to left, 73

73

and so we're moving down the sorted partition. 74

74

Okay, so what do want to do 75

75

if we haven't hit the front of the array 76

76

and if the element at i minus one 77

77

is greater than the element we're inserting? 78

78

Well, if that's the case, 79

79

we want to shift the element at i minus one to the right, 80

80

because we need to make room for this new element, 81

81

so what we're going to do 82

82

is we're going to assign intArray i 83

83

with intArray i minus one, 84

84

and so this is where we're doing the shifting. 85

85

We're shifting from left to right. 86

86

So for example, when we want to insert minus 15, 87

87

assume we've done the first iteration 88

88

and 20 and 35 are in the sorted partition 89

89

when we want to insert minus 15, 90

90

the first unsorted index will be two, 91

91

so i will be two, so we'll say is i greater than zero? 92

92

yes it is. 93

93

Is the value at intArray i minus one, which is 35, 94

94

is that greater than minus 15? 95

95

Well, yes it is. 96

96

So this condition is met, and so what we're going to do is 97

97

we're going to assign intArray two with intArray i minus one 98

98

which is intArray one, 99

99

so we're effectively going to assign 35 to position two, 100

100

and we, you saw this in the slide 101

101

so if you're having trouble 102

102

understanding what's going on here, 103

103

go ahead and look at the slides. 104

104

And then we'll decrement i to one, 105

105

and so on the second iteration, 106

106

we'll say is i greater than zero, 107

107

well, yes it is 108

108

'cause it's one, and we'll say is intArray one minus one, 109

109

which is intArray zero, 110

110

is that greater than the new element, well, yes it is, 111

111

'cause 20 is greater than minus 15 112

112

and so we're gonna shift 20 to the right. 113

113

So we're gonna say that intArray one 114

114

is equal to intArray one minus one, which is zero. 115

115

So 20 will get assigned to position one 116

116

and then we're gonna loop around and subtract one from i 117

117

and at this point, i will be zero, 118

118

so we'll say is i greater than zero? 119

119

Well, no it's not. 120

120

So we'll drop out of the loop 121

121

because we've hit the front of the array. 122

122

Now when we find the correct position, 123

123

what do we need to do? 124

124

Well, our final step when we drop out of this loop 125

125

is to assign intArray i with newElement, 126

126

so in the case we just looked at, 127

127

when we drop out of the loop, i is zero, 128

128

and so we're going to assign minus 15 to intArray zero 129

129

and that's exactly what we want. 130

130

It'll put minus 15 at the front 131

131

and we've shifted 20 and 35 over one. 132

132

And so that's how this implementation works 133

133

and we have finished coding the implementation. 134

134

And so the outer loop is the one 135

135

that's growing the sorted partition by one, 136

136

and the inner loop is that one that's looking 137

137

for the correct position to insert each element 138

138

and is doing the shifting. 139

139

So let's run this to make sure this actually works. 140

140

And indeed it does, we get minus 22, minus 15, 141

141

one, seven, 20, 35, and 55. 142

142

I'll just close that off, and so that is insertion sort. 143

143

It works by taking each element and inserting it 144

144

into its correct position in the sorted partition 145

145

and at the end, when we've gone through all the elements, 146

146

the entire array is the sorted partition. 147

147

And so we're done. 148

148

Okay, now as you can imagine, 149

149

sometimes this will involve a lot of shifting, for example, 150

150

I guess I should remove that comma there, I'll do that, 151

151

for example, in our array, the smallest value in the array 152

152

is right at the end of the array. 153

153

So when we finally hit minus 22, 154

154

we're gonna have to do a lot of shifting, 155

155

we're gonna have to shift every other element 156

156

in the array to the right, to make room for minus 22. 157

157

There can be a lot of shifting with this algorithm 158

158

and so perhaps there is way to improve this algorithm, 159

159

and there is, and we're going to look at that 160

160

in the next video, I'll see you there.