1
00:00:06,760 --> 00:00:10,220
So let's start talking about our sorting algorithms.

2
00:00:10,240 --> 00:00:14,830
We need to start off by having a general understanding of what sorting is.

3
00:00:15,100 --> 00:00:20,440
And I just want to be clear and I want everybody to be on the same page, even though I'm sure everyone

4
00:00:20,440 --> 00:00:23,860
already has a good idea of what it means to sort something.

5
00:00:24,280 --> 00:00:30,250
But again, just so that we are all on the same page, sorting is when we place items in either ascending

6
00:00:30,250 --> 00:00:32,040
or descending order.

7
00:00:32,050 --> 00:00:35,170
So let's depict what that means.

8
00:00:35,170 --> 00:00:41,530
So we'll start off and we'll have a vector of four, three, one and two.

9
00:00:41,530 --> 00:00:44,560
So it's completely unsorted right now.

10
00:00:48,910 --> 00:00:49,900
Unsorted.

11
00:00:50,920 --> 00:00:58,150
If we want to go into ascending order, we have one, two, three and four.

12
00:00:58,600 --> 00:01:05,410
And that would mean that our vector is now sorted in ascending order.

13
00:01:05,410 --> 00:01:06,730
So this is ascending.

14
00:01:06,730 --> 00:01:12,070
So ascending means that our values are in increasing order.

15
00:01:13,210 --> 00:01:26,020
Therefore, if we wanted to do a descending sort, our values would decrease as we sort them out.

16
00:01:26,020 --> 00:01:28,030
So they would be descending.

17
00:01:28,750 --> 00:01:34,400
So what is the purpose of sorting values when we have our items sorted?

18
00:01:34,420 --> 00:01:41,500
It's going to allow us to do a much quicker lookup of an item and there are different algorithms that

19
00:01:41,500 --> 00:01:45,610
we can use to sort a series of values.

20
00:01:46,300 --> 00:01:50,990
And in this lecture we're going to start off by talking about selection sort.

21
00:01:51,010 --> 00:01:57,220
So let's start to look at what selection sort is and how we can perform it.

22
00:01:57,850 --> 00:02:01,420
So we have a selection sort.

23
00:02:05,590 --> 00:02:14,830
So to start off, we will use the exact same vector of values that we had above of four, three, one

24
00:02:14,830 --> 00:02:15,700
and two.

25
00:02:16,150 --> 00:02:21,010
So we want to use selection sort to sort these values.

26
00:02:21,010 --> 00:02:25,570
So we'll do a quick iteration of sorting this using selection sort.

27
00:02:25,840 --> 00:02:34,660
And then we'll look at some pseudocode and then we will do one more selection sort of as an example.

28
00:02:36,070 --> 00:02:44,110
So what we'll do is we'll start here at value four and we'll say that value four is our smallest value.

29
00:02:44,110 --> 00:02:52,030
So we will say the smallest value is currently four.

30
00:02:53,470 --> 00:02:55,590
And now we'll look ahead.

31
00:02:55,600 --> 00:02:59,260
So we will say I plus 1i4 index.

32
00:02:59,920 --> 00:03:06,310
So we are currently at index zero and we will look through the rest of the array and find the smallest

33
00:03:06,310 --> 00:03:06,960
value.

34
00:03:06,970 --> 00:03:09,840
So three is smaller than four.

35
00:03:09,850 --> 00:03:17,070
So our new smallest value is technically three, but then our next index, we have one.

36
00:03:17,080 --> 00:03:23,550
So our new smallest value is now one, and then we have two and two is not less than one.

37
00:03:23,560 --> 00:03:28,780
So what we will do is we will swap one and four.

38
00:03:29,800 --> 00:03:36,010
So our new array looks like one, three, four and two.

39
00:03:37,270 --> 00:03:43,840
So now that we have done one iteration through the array and we know that one is in the correct spot,

40
00:03:43,840 --> 00:03:50,290
we will now start with this index and then this will be a plus one.

41
00:03:51,100 --> 00:03:54,070
So now we have three.

42
00:03:54,070 --> 00:03:59,170
So our smallest value now is three.

43
00:03:59,950 --> 00:04:00,970
Actually, we'll do it this way.

44
00:04:00,970 --> 00:04:06,100
So we went for we had four, three.

45
00:04:06,800 --> 00:04:07,370
One.

46
00:04:07,610 --> 00:04:13,850
So now we will have our smallest vowel here and it is currently three.

47
00:04:13,970 --> 00:04:15,500
So we look at four.

48
00:04:15,890 --> 00:04:19,370
Four is not less than three, but so now we look at two.

49
00:04:19,580 --> 00:04:21,170
Two is less than three.

50
00:04:21,170 --> 00:04:26,690
So we can get rid of three, put two there and now we will swap.

51
00:04:28,450 --> 00:04:29,530
Three and two.

52
00:04:30,430 --> 00:04:35,380
So now we have one, two, four and three.

53
00:04:39,620 --> 00:04:42,050
So we know that one and two are sorted now.

54
00:04:42,470 --> 00:04:47,180
So we are back to looking at four and then this is AI plus one.

55
00:04:47,780 --> 00:04:54,080
So in this case, our smallest vowel is four.

56
00:04:54,080 --> 00:04:59,560
Again, when we compare four and three, we see that three is obviously less.

57
00:04:59,570 --> 00:05:08,000
So we swap them now and we have one, two, three and four.

58
00:05:08,420 --> 00:05:13,880
So now our vector is sorted and ascending order just like how we wanted.

59
00:05:14,870 --> 00:05:22,550
So now that we have a general idea of how selection sort works, how could we code this out?

60
00:05:23,270 --> 00:05:42,290
Well, we could say four I in zero two, size minus one, and then we want four J So I in this case

61
00:05:42,290 --> 00:05:45,040
is referring to where we start at.

62
00:05:45,050 --> 00:05:54,230
So this was I here, this was I here, I was here and then we were sorted and then J was always one

63
00:05:54,230 --> 00:05:54,950
step ahead.

64
00:05:54,950 --> 00:06:00,090
So this was J plus one J plus one J plus one.

65
00:06:00,110 --> 00:06:03,260
So now we have four J.

66
00:06:06,420 --> 00:06:12,360
In one to size.

67
00:06:13,170 --> 00:06:16,380
So that gives us the correct index that we are looking for.

68
00:06:16,710 --> 00:06:19,290
And then we want to just do our simple checks.

69
00:06:19,500 --> 00:06:21,600
So we have our smallest value.

70
00:06:24,160 --> 00:06:25,690
Well, let's get rid of that.

71
00:06:26,080 --> 00:06:26,950
If.

72
00:06:29,980 --> 00:06:32,680
Smallest vow.

73
00:06:36,500 --> 00:06:37,430
Is greater.

74
00:06:38,370 --> 00:06:38,970
Then I.

75
00:06:39,790 --> 00:06:43,210
Then we want to make our small value.

76
00:06:45,950 --> 00:06:50,570
Equal to AI, because then we know AI is less than our smallest value.

77
00:06:52,280 --> 00:07:04,580
And then when we have iterated through all of the elements, we want to simply swap I in the smallest

78
00:07:04,580 --> 00:07:05,150
value.

79
00:07:07,640 --> 00:07:10,580
And that is all we really have to do.

80
00:07:11,120 --> 00:07:12,780
For this code to work.

81
00:07:12,830 --> 00:07:22,130
We just go through each iteration and we want to find the smallest value and then swap them, because

82
00:07:22,130 --> 00:07:26,930
then we know that that index is completely sorted and in the correct order.

83
00:07:27,590 --> 00:07:33,590
So when we're looking at this pseudo code, we see that our big zero notation, just keeping this in

84
00:07:33,590 --> 00:07:36,920
mind is going to be o of n squared.

85
00:07:37,220 --> 00:07:46,040
We have two nested for loops that are iterating the size of of of our vector, so we know that our big

86
00:07:46,040 --> 00:07:47,900
O is going to be in squared.

87
00:07:48,560 --> 00:07:54,860
So not the most performant method, but it does the job.

88
00:07:55,340 --> 00:08:00,440
So let's do one more example of this.

89
00:08:00,800 --> 00:08:08,390
So let's get down here some and we will do a new array of values.

90
00:08:08,390 --> 00:08:12,230
510, one.

91
00:08:13,020 --> 00:08:15,390
For an 11.

92
00:08:17,880 --> 00:08:24,060
So this is our new vector, and we're going to keep our algorithm, our pseudocode, up here in mind.

93
00:08:24,810 --> 00:08:35,640
So this is going to be our AI value, and this is going to be our plus one value, which means our small

94
00:08:35,640 --> 00:08:38,340
value in this case is equal to five.

95
00:08:38,880 --> 00:08:41,580
So J plus one is ten.

96
00:08:41,580 --> 00:08:45,750
Is is five greater than ten?

97
00:08:45,750 --> 00:08:46,440
No.

98
00:08:46,680 --> 00:08:48,720
Is five greater than one?

99
00:08:50,040 --> 00:08:50,870
Yes, it is.

100
00:08:50,880 --> 00:08:55,440
So now we will replace the smallest value with one.

101
00:08:55,740 --> 00:08:58,160
Is one greater than four?

102
00:08:58,170 --> 00:08:58,650
No.

103
00:08:58,650 --> 00:09:00,090
Is one greater than 11?

104
00:09:00,090 --> 00:09:00,510
No.

105
00:09:00,510 --> 00:09:02,160
So now we do our swap.

106
00:09:02,310 --> 00:09:08,580
So now we swap five because that was I and our smallest value of one.

107
00:09:08,670 --> 00:09:16,620
So our new array now looks like 110, five, four, 11.

108
00:09:20,380 --> 00:09:26,530
And now that we know that one is completely separate, completely sorted, and definitely in the correct

109
00:09:26,530 --> 00:09:27,130
order.

110
00:09:27,160 --> 00:09:30,190
Our new eye is now ten.

111
00:09:30,340 --> 00:09:32,800
And this is our plus one.

112
00:09:33,310 --> 00:09:37,240
So our small vowel is equal to ten.

113
00:09:38,410 --> 00:09:40,660
Is ten greater than five?

114
00:09:40,690 --> 00:09:41,710
Yes, it is.

115
00:09:42,610 --> 00:09:44,440
Is five greater than four?

116
00:09:45,190 --> 00:09:46,390
Yes, it is.

117
00:09:46,720 --> 00:09:48,400
Is four greater than 11?

118
00:09:48,430 --> 00:09:49,210
No.

119
00:09:49,420 --> 00:09:54,700
So now we want to swap ten, because that is I and our four.

120
00:09:55,660 --> 00:10:02,110
So now we have one, four, five, ten and 11.

121
00:10:05,740 --> 00:10:07,420
So now this is our eye.

122
00:10:07,870 --> 00:10:09,670
This is our plus one.

123
00:10:10,630 --> 00:10:12,130
We do our comparisons.

124
00:10:12,130 --> 00:10:13,510
We see our small vowel.

125
00:10:15,900 --> 00:10:17,280
Is equal to five.

126
00:10:17,880 --> 00:10:20,010
Is five greater than ten?

127
00:10:20,010 --> 00:10:20,520
No.

128
00:10:20,520 --> 00:10:21,990
Is five greater than 11?

129
00:10:21,990 --> 00:10:22,600
No.

130
00:10:22,620 --> 00:10:26,790
So now we can do we don't have to do anything increment up.

131
00:10:26,790 --> 00:10:30,720
So ten is now our IE and 11 is our plus one.

132
00:10:31,350 --> 00:10:37,410
In this case, our small vowel is equal to ten.

133
00:10:37,620 --> 00:10:40,050
Is ten greater than 11?

134
00:10:40,050 --> 00:10:40,670
No.

135
00:10:40,680 --> 00:10:47,430
We now hit the end of the array, so we know for sure that our array is now sorted.

136
00:10:48,600 --> 00:10:52,230
So now that is how selection sort works.

137
00:10:52,230 --> 00:11:01,170
We are now going to implement this algorithm in our next lecture and if you have any questions at any

138
00:11:01,170 --> 00:11:05,070
point, please feel free to ask them in the Q&A section.