1
00:00:00,420 --> 00:00:04,090
‫So now let's look at the big O of quicksort.

2
00:00:04,110 --> 00:00:06,120
‫So I'm going to bring up an array like this.

3
00:00:06,630 --> 00:00:13,260
‫And when we run pivot, it brings us to a point like this.

4
00:00:14,020 --> 00:00:21,160
‫So the first thing I want to point out about this is we didn't have to create any new items here.

5
00:00:21,160 --> 00:00:24,880
‫We just move things around within the same array.

6
00:00:25,390 --> 00:00:33,250
‫So this is different than merge sort that creates new items and therefore doubles the amount of space

7
00:00:33,250 --> 00:00:34,630
‫that it takes up in memory.

8
00:00:34,900 --> 00:00:41,410
‫With this, you are working only within the original array without duplicating any data.

9
00:00:41,410 --> 00:00:50,050
‫So from a space complexity perspective, this is of one and this is an advantage of quicksort over something

10
00:00:50,050 --> 00:00:51,580
‫like merge sort.

11
00:00:52,420 --> 00:00:58,210
‫From a time complexity perspective in order to move all of these items around like we just did here.

12
00:00:58,840 --> 00:01:05,560
‫That was O of NW because we had a for loop that went from the beginning of the array all the way through

13
00:01:05,560 --> 00:01:06,610
‫to the end.

14
00:01:07,150 --> 00:01:13,300
‫And if you look at how many times we had to do this, this was one then we did it to.

15
00:01:14,210 --> 00:01:14,930
‫Three.

16
00:01:15,830 --> 00:01:18,290
‫That is going to be log in.

17
00:01:18,990 --> 00:01:27,610
‫So what we just did here is, oh, within times log in and we'll look at this on the graph like this.

18
00:01:27,630 --> 00:01:29,880
‫It's much better than oh of n squared.

19
00:01:30,360 --> 00:01:36,960
‫But the problem with this is what I just showed you is actually the best case for quicksort.

20
00:01:36,990 --> 00:01:41,400
‫The worst case is not o of n times log n.

21
00:01:41,490 --> 00:01:43,410
‫So now let's look at the worst case.

22
00:01:43,650 --> 00:01:48,510
‫The worst case is if you have already sorted data.

23
00:01:48,870 --> 00:01:52,230
‫So if we take that first item there, we make that our pivot point.

24
00:01:52,920 --> 00:01:57,480
‫We're going to compare that to all the other items in the array and that is not going to move.

25
00:01:57,480 --> 00:01:59,070
‫So I'll colour that in green.

26
00:01:59,370 --> 00:02:05,760
‫But what we normally do with quicksort is we run quicksort on all the items on the left of it, all

27
00:02:05,760 --> 00:02:09,960
‫the ones that are less than, and then run it also on everything on the right.

28
00:02:10,380 --> 00:02:15,330
‫It is that splitting of the array that makes it efficient.

29
00:02:15,510 --> 00:02:21,570
‫But in this case there are no items on the left, there are only items on the right, so there is no

30
00:02:21,570 --> 00:02:23,880
‫splitting of the array.

31
00:02:24,330 --> 00:02:31,470
‫And the same is true when we look at two, we compare it with everything else and there are only items

32
00:02:31,470 --> 00:02:35,340
‫on the right and for three as well and so on.

33
00:02:36,100 --> 00:02:38,440
‫And so on, all the way to the end.

34
00:02:39,780 --> 00:02:45,720
‫So in this circumstance, this is actually o of n squared.

35
00:02:46,660 --> 00:02:51,760
‫That is our worst possible scenario and that is what bigo measures.

36
00:02:52,240 --> 00:02:59,010
‫So our best case or average case would be o of in times log in, but our worst case is o of n squared.

37
00:02:59,020 --> 00:03:05,020
‫So if you have sorted or almost sorted data, this is not a good sorting algorithm.

38
00:03:05,380 --> 00:03:09,100
‫But if you have random data, this is an excellent sorting algorithm.

39
00:03:09,100 --> 00:03:15,340
‫It's very fast and the space complexity is o of one which is better than merge sort.

40
00:03:15,700 --> 00:03:19,730
‫If your data is sorted, it would be better to use something like insertion sort.

41
00:03:19,750 --> 00:03:22,770
‫Even though that's o of n squared is this worst case.

42
00:03:22,780 --> 00:03:27,340
‫If you're using sorted or almost sorted data, it is very efficient.

43
00:03:27,340 --> 00:03:29,650
‫It actually runs at O of n.

44
00:03:30,660 --> 00:03:31,000
‫Okay.

45
00:03:31,050 --> 00:03:33,270
‫And that is our overview of QuickSort.

46
00:03:34,100 --> 00:03:35,060
‫Bego.