1
00:00:06,190 --> 00:00:09,640
In this lecture, we are going to start talking about QuickSort.

2
00:00:10,750 --> 00:00:17,110
QuickSort is going to be another divide and conquer algorithm that is also going to use recursion.

3
00:00:17,320 --> 00:00:24,730
So kind of similar to what we did for Merge sort in the previous lecture with this being the last sorting

4
00:00:24,730 --> 00:00:30,310
algorithm that we are going to talk to, I am going to make this an assignment for you to try to implement

5
00:00:30,310 --> 00:00:31,270
it on your own.

6
00:00:32,710 --> 00:00:39,190
And by the end of this lecture you will have the confidence to attempt implementing it on your own.

7
00:00:39,190 --> 00:00:44,260
And if you get stuck at any point, please feel free to ask some questions in the Q&A section and I

8
00:00:44,260 --> 00:00:49,360
will get back to you pretty quickly on how to get unstuck and continue moving forward.

9
00:00:50,200 --> 00:00:57,280
After you give an attempt on the assignment, the next lecture will be my solution to implementing in

10
00:00:57,280 --> 00:00:58,030
QuickSort.

11
00:00:58,780 --> 00:01:04,510
So let's start taking a look at what QuickSort is and how it works.

12
00:01:04,960 --> 00:01:10,660
So the first thing I want to do is I want to create an array with some elements in there.

13
00:01:10,660 --> 00:01:20,740
So we're going to have eight, five, one, two, seven, three and four.

14
00:01:24,860 --> 00:01:26,090
And then here.

15
00:01:29,230 --> 00:01:32,020
We need to have something called a pivot.

16
00:01:32,890 --> 00:01:35,590
And there's many ways to come up with a pivot.

17
00:01:35,590 --> 00:01:40,660
But for simplicity, I'm going to make the last element in our array the pivot.

18
00:01:43,920 --> 00:01:47,430
So in this case, four is the pivot.

19
00:01:48,240 --> 00:01:53,790
And then we're going to have two variables I and J that are going to iterate over the rest of these

20
00:01:53,790 --> 00:02:00,360
elements and help us begin figuring out where this pivot goes.

21
00:02:00,690 --> 00:02:08,280
Because after we're done with our first iteration, we want four to be in the correct spot in this array.

22
00:02:08,460 --> 00:02:13,260
So we know that the array is going to be one, two, three, four, five, seven, eight.

23
00:02:13,260 --> 00:02:17,430
So one, two, three, four, five, seven, eight.

24
00:02:17,430 --> 00:02:20,670
So we want to get four into this spot here.

25
00:02:20,670 --> 00:02:27,150
This is our goal through the first iteration, but also with four being here.

26
00:02:27,150 --> 00:02:35,730
We also want to make sure that we have one, two and three in no particular order and this in these

27
00:02:35,730 --> 00:02:36,570
three spots.

28
00:02:36,570 --> 00:02:42,090
So when four is here, every element down here should be less than four.

29
00:02:42,120 --> 00:02:47,130
It could be one, two, three, it could be three, two, one, it could be two, one, three, and

30
00:02:47,130 --> 00:02:48,480
so on and so forth.

31
00:02:49,350 --> 00:02:51,540
But then the same applies for up here.

32
00:02:51,570 --> 00:03:02,070
We would want every element greater than four to already be in an index, greater than where our four

33
00:03:02,070 --> 00:03:03,140
element is.

34
00:03:03,150 --> 00:03:07,350
That way we can begin doing QuickSort on these elements as well.

35
00:03:07,350 --> 00:03:09,960
So that's where the recursive approach comes into.

36
00:03:10,050 --> 00:03:16,020
Once we have four and its correct spot, well we no longer have to worry about four, but now we can

37
00:03:16,020 --> 00:03:21,240
call quicksort on these elements and then we'd be able to call quicksort on these elements.

38
00:03:21,990 --> 00:03:26,550
So let's go ahead and run through this real quick and kind of see what this looks like.

39
00:03:26,940 --> 00:03:32,370
So we will say that AI is here and J is here.

40
00:03:34,380 --> 00:03:39,360
And what we're going to do is AI is going to look for numbers greater than four.

41
00:03:39,360 --> 00:03:45,360
So I greater than four and J is going to look for numbers less than four.

42
00:03:46,650 --> 00:03:51,090
Well, luckily, we actually don't have to look too hard to find that.

43
00:03:51,090 --> 00:03:58,620
So we see we have an AI, which is a greater value than our pivot and we have J, which is a value less

44
00:03:58,620 --> 00:03:59,490
than our pivot.

45
00:03:59,760 --> 00:04:03,300
So what we're going to do here is we're actually going to swap these values.

46
00:04:03,300 --> 00:04:09,960
So now we have 351, two, seven, eight and four.

47
00:04:12,750 --> 00:04:21,690
So this is going to be our new array currently and now we're going to decrement J So J will go here

48
00:04:21,690 --> 00:04:24,540
and now we're going to increase AI.

49
00:04:24,690 --> 00:04:32,250
So remember, we're looking for values of AI greater than four and J less than four.

50
00:04:32,250 --> 00:04:35,340
So AI is currently greater than four.

51
00:04:35,340 --> 00:04:38,670
So we will leave that as j less than four.

52
00:04:38,700 --> 00:04:43,080
It is not so we will go ahead and decrement it.

53
00:04:43,860 --> 00:04:46,620
So now two is less than four.

54
00:04:46,620 --> 00:04:49,590
So now we will swap these values.

55
00:04:50,370 --> 00:04:53,460
So our new array is 3 to 1.

56
00:04:55,460 --> 00:04:56,340
Five.

57
00:04:56,360 --> 00:04:57,380
Seven.

58
00:04:57,650 --> 00:04:59,780
Eight and four.

59
00:05:03,540 --> 00:05:05,160
So our value.

60
00:05:06,240 --> 00:05:07,980
Is now where the five is.

61
00:05:11,350 --> 00:05:14,400
Now we're going to increment I by one.

62
00:05:14,410 --> 00:05:16,150
Well, as I greater than four.

63
00:05:16,180 --> 00:05:16,810
No.

64
00:05:17,170 --> 00:05:20,590
So now we will cross that out and increment it by one.

65
00:05:20,800 --> 00:05:29,650
Well now we see that I and J are at the exact same position, which now means that our pivot and we'll

66
00:05:29,650 --> 00:05:31,150
just keep them circled that way.

67
00:05:31,150 --> 00:05:32,530
We know it's our pivot.

68
00:05:32,980 --> 00:05:36,400
Now we know our pivot actually goes here.

69
00:05:36,820 --> 00:05:41,520
So now we swap this five with our pivot.

70
00:05:41,530 --> 00:05:50,350
So now our index is three, two, one, four, seven, eight and five.

71
00:05:50,830 --> 00:05:56,770
And now, if you remember at the beginning of this lecture, I said, when our four is in the correct

72
00:05:56,770 --> 00:06:03,370
index, we want to make sure every value to the left of it is below four, and every value to the right

73
00:06:03,370 --> 00:06:04,920
of it is above four.

74
00:06:04,930 --> 00:06:11,030
And you can see that that is the outcome of our first iteration.

75
00:06:11,050 --> 00:06:15,250
So now we know four is in the correct spot.

76
00:06:18,110 --> 00:06:23,990
So now we would take our recursive approach and we would call QuickSort here

77
00:06:26,810 --> 00:06:30,860
and we would call quicksort here.

78
00:06:34,460 --> 00:06:40,130
And then we would keep doing that until the array is correctly sorted.

79
00:06:40,850 --> 00:06:43,640
And that's exactly how QuickSort works.

80
00:06:43,640 --> 00:06:46,180
So you can see that it's a pretty efficient algorithm.

81
00:06:46,190 --> 00:06:54,200
So now what we want to do is we want to take a look at the pseudocode so that you can have a good idea

82
00:06:54,200 --> 00:06:58,250
of what we need to do in order to implement this code in.

83
00:06:58,850 --> 00:07:01,370
So we're going to have our QuickSort function.

84
00:07:04,370 --> 00:07:06,950
And it's going to take a couple of parameters.

85
00:07:06,950 --> 00:07:09,050
We'll take our our vector.

86
00:07:10,130 --> 00:07:12,190
We're going to take low.

87
00:07:12,200 --> 00:07:22,400
So the beginning of the Array's index and then the high, which is the ending array, excuse me, the

88
00:07:22,400 --> 00:07:24,200
end index of the array.

89
00:07:25,490 --> 00:07:39,260
So what we want to do in here is check if low is less than high, and then we will say pi and this pi

90
00:07:39,260 --> 00:07:44,030
equals r partitioning

91
00:07:46,010 --> 00:07:47,060
index.

92
00:07:49,780 --> 00:08:06,220
So we want to do pi is equal to partition or partition and we want to pass in our array our low and

93
00:08:06,220 --> 00:08:07,030
our high.

94
00:08:08,050 --> 00:08:12,640
And then when we get our partitioning index, we want to call quicksort.

95
00:08:17,140 --> 00:08:25,510
On the array, on the low, and then the partitioning index minus one.

96
00:08:26,290 --> 00:08:28,120
And then we also want to call QuickSort.

97
00:08:28,120 --> 00:08:30,250
So that would be the left side.

98
00:08:30,250 --> 00:08:31,690
This is the left side.

99
00:08:32,360 --> 00:08:40,060
Now we want to call it on the array partitioning index plus one and then the high.

100
00:08:40,660 --> 00:08:49,060
So remember, this is going to be the left side and this will be the right side.

101
00:08:49,060 --> 00:08:52,840
So left meaning over here, right meaning over here.

102
00:08:52,840 --> 00:08:57,580
And then for in this case is our partitioning index.

103
00:08:58,390 --> 00:09:01,420
And that is all we want to do for QuickSort.

104
00:09:01,420 --> 00:09:05,560
So we'll just kind of wrap all this up right here.

105
00:09:05,560 --> 00:09:12,790
That way we know that this is QuickSort, so we see that we have another function call in here called

106
00:09:13,360 --> 00:09:14,860
called partition.

107
00:09:16,090 --> 00:09:24,430
So now we need to create a partition, some partition pseudocode.

108
00:09:24,610 --> 00:09:33,880
So we're going to have partition and partition is going to take our array, it's going to take our low

109
00:09:34,420 --> 00:09:36,070
and it's going to take our high.

110
00:09:37,960 --> 00:09:40,480
And then in here we're going to get our pivot.

111
00:09:40,480 --> 00:09:41,140
So.

112
00:09:44,840 --> 00:09:47,300
Pivot is equal to.

113
00:09:47,300 --> 00:09:49,880
And then in our case, it was our high index.

114
00:09:49,880 --> 00:09:59,000
So the last element, so we want to set it to array of high and then I is going to be equal to zero

115
00:09:59,000 --> 00:10:00,050
in our case.

116
00:10:00,230 --> 00:10:05,660
And then we will set J also to high minus one.

117
00:10:08,960 --> 00:10:11,210
So now we want to implement in.

118
00:10:12,740 --> 00:10:23,930
If J is less than we want to find a j, less than our pivot and an eye greater than our pivot, that

119
00:10:23,930 --> 00:10:25,550
way we can start sorting them out.

120
00:10:25,910 --> 00:10:30,050
So if J is less than pivot

121
00:10:32,660 --> 00:10:50,000
and also AI is greater than pivot, then we want to swap i, I and J and then you want to increment

122
00:10:50,000 --> 00:10:53,240
I and you also want to increment J.

123
00:10:55,580 --> 00:11:08,210
And then once the index of I and J is the same so we can say something along the lines of if.

124
00:11:10,150 --> 00:11:23,840
A ray of j is less than the pivot, meaning we have passed that midway point then we're going to want

125
00:11:23,840 --> 00:11:24,770
to swap.

126
00:11:32,310 --> 00:11:34,410
I plus one.

127
00:11:35,950 --> 00:11:38,170
And our pivot.

128
00:11:39,930 --> 00:11:40,560
That way.

129
00:11:40,560 --> 00:11:43,350
This puts it in the middle.

130
00:11:46,370 --> 00:11:48,470
And this will put pivot.

131
00:11:50,320 --> 00:11:51,100
In.

132
00:11:52,710 --> 00:11:55,860
Correct location.

133
00:11:57,210 --> 00:12:00,420
Let's be a little bit more specific in the correct index.

134
00:12:05,860 --> 00:12:06,490
Right.

135
00:12:07,000 --> 00:12:13,630
So, again, we're checking to see if Jay is less than pivot and if eye is greater than pivot.

136
00:12:13,930 --> 00:12:22,630
Then we want to swap I and J, and then we also want to increment until this condition is satisfied.

137
00:12:24,420 --> 00:12:29,370
And then once a ray of j is less than the pivot.

138
00:12:31,030 --> 00:12:32,740
Then you want to swap.

139
00:12:34,360 --> 00:12:36,930
Let's actually let's redo this part.

140
00:12:36,940 --> 00:12:43,120
Make it a little clearer, because if a red j is less than the pivot.

141
00:12:44,810 --> 00:12:50,390
That means all of our values are are now correctly on the left side.

142
00:12:50,690 --> 00:12:55,160
So at that point, we just want to swap.

143
00:12:56,800 --> 00:12:57,970
J and pivot.

144
00:13:01,720 --> 00:13:06,550
And there's other ways that you can swap here, because remember, at some point I and Jay are going

145
00:13:06,550 --> 00:13:07,510
to intersect.

146
00:13:08,200 --> 00:13:10,150
So that is when you want to swap.

147
00:13:10,750 --> 00:13:14,710
So let's just make a note of that when I.

148
00:13:15,870 --> 00:13:19,470
And J intersect.

149
00:13:21,930 --> 00:13:24,840
Swap with.

150
00:13:29,930 --> 00:13:41,510
Because then that'll put pivot in the correct spot and the correct index will be in correct.

151
00:13:43,440 --> 00:13:44,370
Index.

152
00:13:46,040 --> 00:13:50,540
And then that's all we have to do for our partitioning function.

153
00:13:51,630 --> 00:13:56,050
So again, take some time to try to implement this on your own.

154
00:13:56,070 --> 00:14:02,430
If you have any issues, please feel free to ask them in the Q&A section and I'll be more than happy

155
00:14:02,940 --> 00:14:05,130
to provide you with some assistance.

156
00:14:05,400 --> 00:14:11,100
And then once you have given it a go, please proceed to the next lecture while I will implement my

157
00:14:11,100 --> 00:14:13,080
solution to this assignment.