Original subtitles

1 1

(techno music) 2

2

All right, so in this video, 3

3

we're going to take a look at the selection sort algorithm. 4

4

Now this algorithm divides the array 5

5

into sorted and unsorted partitions 6

6

just like bubble sort does. 7

7

And what we do is we traverse the array 8

8

and we look for the largest element 9

9

in the unsorted partition. 10

10

And when we find it, 11

11

we swap it with the last element in the unsorted partition. 12

12

And at that point, 13

13

that swapped element will be its correct sorted position. 14

14

And so just like with bubble sort, 15

15

at the beginning of the algorithm, 16

16

the entire array is unsorted 17

17

so the last unsorted index is six 18

18

and just like with bubble sort 19

19

we're going to grow the sorted partition from right to left. 20

20

We're going to initialise a largest field to zero 21

21

so when we start we say you know what, 22

22

20 is the largest element that we know about so far, 23

23

so whatever is at position zero will be the largest element. 24

24

And we're going to start 25

25

by comparing the element at position one 26

26

to whatever is at position zero, 27

27

so we're gonna start with i equal to one. 28

28

We're going to use i to traverse the unsorted partition 29

29

and find the largest element 30

30

and so these are our initial values. 31

31

The last unsorted index is six 32

32

because the entire array is unsorted, i is one. 33

33

We're gonna start our traversal here 34

34

and we've initialised the largest. 35

35

The largest will contain the index of the largest element. 36

36

Then the unsorted partition, that's initialised to zero. 37

37

So we're going to compare 35 to 20 and we're gonna say hey, 38

38

35 is larger than 20 and because of that, 39

39

we're going to change largest to one 40

40

and then we're gonna increment i to two 41

41

and we're gonna compare minus 15 to the largest element 42

42

which is now at position one 43

43

and we're gonna say well minus 15 is less than 35 44

44

so we're just gonna increment i to three. 45

45

We're gonna compare seven to the largest element 46

46

which is still at position one. 47

47

Seven is less than 35 so we just increment i to four. 48

48

We're now gonna compare 55 to 35 49

49

and 55 is greater than 35 50

50

so at this point we're going to change largest to four 51

51

because the largest element we found so far 52

52

in the unsorted partition is at index four 53

53

and we increment i to five. 54

54

We compare one to 55. 55

55

Well, one is less than 55 so we just increment i to six. 56

56

We compare minus 22 to 55. 57

57

Minus 22 is less than 55 so we don't do anything. 58

58

And at this point, i is equal to the last unsorted index 59

59

and so we have completed our first traversal of the array. 60

60

So we're going to swap the largest element 61

61

that we found in the unsorted partition 62

62

and that's at position four with the last element 63

63

in the unsorted partition and that's at position six. 64

64

So what we're gonna do is swap 55 and minus 22 65

65

and we have now completed our first traversal. 66

66

And at this point, 55 is in its correct sorted position 67

67

and so we're gonna decrement last unsorted index to five 68

68

and we're gonna re-initialize i to one 69

69

and we're going to say the largest element 70

70

in the unsorted partition is at position zero 71

71

and we repeat the process. 72

72

So we're going to compare 35 against 20. 73

73

35 is greater than 20 so we're gonna set largest to one. 74

74

Now we increment i to two 75

75

and we compare minus 15 against 35 76

76

'cause 35 is now the largest element. 77

77

Minus 15 is less than 35 so we just increment i to three. 78

78

Seven is less than 35 so we just increment i to four. 79

79

Minus 22 is less than 35 so we just increment i to five 80

80

and of course one is less than 35 and at this point, 81

81

i equals the last unsorted index 82

82

so we have completed our second traversal of the array. 83

83

And what we wanna do at this point 84

84

is swap the largest element, which is at position one, 85

85

with the last element in the unsorted partition, 86

86

which is at index five, 87

87

and so we're going to swap 35 and one. 88

88

And at this point, 89

89

35 and 55 are in their correct sorted positions 90

90

and we decrement the last unsorted index 91

91

and so now the last unsorted index 92

92

of the unsorted partition is four 93

93

and we would re-initialize largest to zero 94

94

and that should be a one. 95

95

We should re-initialize i to one. 96

96

And we're just gonna repeat the process. 97

97

We're gonna compare one to 20, 98

98

largest is gonna remain zero, et cetera, 99

99

until the entire array is sorted 100

100

and so this is how selection sort works 101

101

and it's called selection sort because on each traversal 102

102

where it's selecting the largest element 103

103

and removing it into the sorted partition. 104

104

So selection sort is an in-place algorithm. 105

105

It doesn't use any extra memory. 106

106

As I said with bubble sort, 107

107

it's okay to use a few extra fields 108

108

as long as the extra memory you're using 109

109

doesn't depend on the number of items you're sorting, 110

110

it's an in-place algorithm. 111

111

It's a quadratic algorithm 112

112

so it has a time complexity of O to the n squared 113

113

because we have n elements in the array 114

114

and for each element we traverse n elements, 115

115

so it's quadratic. 116

116

However, it doesn't require as much swapping as bubble sort. 117

117

You'll notice that we only swap once per traversal 118

118

and so selection sort will usually perform better 119

119

than bubble sort. 120

120

I say usually because depending on 121

121

you might have an array that's almost sorted 122

122

and so bubble sort doesn't have to swap that much, 123

123

but in the average case, all other things being equal, 124

124

generally selection sort will perform better. 125

125

However, selection sort is an unstable algorithm 126

126

and you can see why, right? 127

127

Because if we have duplicate elements, 128

128

there's no guarantee that their original order 129

129

relative to each other will be preserved 130

130

because on each pass, 131

131

we swapped the largest element 132

132

with whatever is occupying the last position 133

133

in the unsorted partition 134

134

and so it's very possible 135

135

that we could take the second duplicate value 136

136

and move it in front of its twin. 137

137

So because of that, selection sort is an unstable algorithm. 138

138

So if you need a stable sort algorithm, 139

139

then you don't wanna be using selection sort. 140

140

Okay, so that's it for the theory. 141

141

Let's move on and implement selection sort. 142

142

Ill see you in the next video.