Original subtitles

1 1

(lively music) (keyboard clacking) 2

2

So, let's implement Selection Sort. 3

3

Now as I said, when I implemented bubble sort, 4

4

I'm not going to create the projects on screen anymore, 5

5

so I've created a new project, 6

6

I'm putting the code into package 7

7

academy.learnprogramming.selectionsort. 8

8

I've added our array, I've added the code 9

9

to print the array and I've added the swap method 10

10

that I wrote in the bubble sort video, 11

11

so if you didn't watch that video 12

12

or you need a review of what this method is doing, 13

13

you can go back and watch that video, 14

14

so let's get cracking on selection sort. 15

15

So, we're gonna say for int lastUnsortedIndex 16

16

equals and once again, this will be intArray.length 17

17

minus one because at the beginning of the implementation, 18

18

the entire array is unsorted, 19

19

it's in the unsorted partition 20

20

and so, the lastUnsortedIndex will be the last valid index 21

21

in the array which is six. 22

22

Now it's length minus one. 23

23

And we wanna keep going 24

24

as long as the lastUnsortedIndex is greater than zero. 25

25

Once it hits zero, that means the entire array is sorted 26

26

and we're going to decrement this on each iteration, 27

27

so this is starting out exactly 28

28

the same way bubble sort started. 29

29

So, we're gonna initialise our largest index to zero, 30

30

so right now we're saying that in the unsorted partition, 31

31

the largest element is at position zero 32

32

'cause we haven't actually looked at anything yet 33

33

and then we're gonna say for int i equals one, 34

34

i is less than or equal to the lastUnsortedIndex, 35

35

i++ and what we wanna do 36

36

is we want to traverse the unsorted partition 37

37

and look for the largest element, 38

38

so we're going to start at one 39

39

'cause we've initialised largest to zero, 40

40

so we wanna say is the element at position one greater 41

41

than the largest element that we know about so far? 42

42

Because if it is, then we need to update largest 43

43

and we're gonna do that until we hit the end 44

44

of the unsorted partition. 45

45

Now, unlike with bubble sort, 46

46

we do need to check the element in the last position, 47

47

in bubble sort, we didn't need the equals 48

48

because we were comparing i against i plus one 49

49

and so, the last index we wanted to check 50

50

was lastUnsortedIndex minus one 51

51

against lastUnsortedIndex 52

52

but here we wanna compare every element 53

53

against whatever's largest, 54

54

so we need to compare this last element as well. 55

55

So, that's what the equals is doing here 56

56

and so, that's what we wanna do. 57

57

We wanna say if intArray i 58

58

is greater than intArray largest 59

59

because that's the largest element we know about so far, 60

60

then we wanna update largest to i. 61

61

So, we're gonna compare 35 against 20 62

62

on this first iteration. 63

63

35 is bigger than 20 64

64

and so, largest is gonna get updated to one 65

65

and then on the next iteration, 66

66

we're gonna be comparing against 35 67

67

because that's the largest element we found so far. 68

68

So, once we drop out of this loop, 69

69

what do we wanna do? 70

70

Well, we wanna swap the largest element that we found 71

71

with the last element in the unsorted partition, 72

72

so with the element that's sitting at lastUnsortedIndex. 73

73

And so, we can use our handy swap method to do that, 74

74

so we'll pass intArray 75

75

and we'll pass largest and lastUnsortedIndex. 76

76

And that's it. 77

77

We have implemented selection sort. 78

78

So, once again, if you're having trouble understanding this, 79

79

review the last video 80

80

where we go through this by hand with the slide. 81

81

So, the outer loop is the one that's increasing 82

82

the sorted partition by one, 83

83

it's growing it from right to left 84

84

and the inner loop is the one 85

85

that's looking for the largest element 86

86

and then once we've looked at all the elements 87

87

and we know which one is the largest, 88

88

at that point, we're gonna swap the largest element 89

89

with the last element in the unsorted partition 90

90

and when we look back around, 91

91

of course at that point, 92

92

we have grown the sorted partition by one 93

93

and so, we subtract one from the lastUnsortedIndex. 94

94

So, let's run this, let's see if this actually works. 95

95

And it does. 96

96

Here's our sorted array. 97

97

Minus 22, minus 15, one, seven, 20, 35 and 55. 98

98

And I'll just close this off. 99

99

Now as I said, this is a quadratic algorithm, 100

100

O to the n squared 101

101

and once again, we have two loops 102

102

and I said that that's a hint 103

103

because usually each loop can be considered n 104

104

and so, we have n times n 105

105

and that gives us O to the n squared. 106

106

So, that's selection sort. 107

107

On each traversal of the array, 108

108

it selects the largest value 109

109

and it adds it into the sorted partition. 110

110

I'll see you in the next video.