1
00:00:01,010 --> 00:00:05,340
- Hey there, welcome to
week eight of CS 124 online,
2
00:00:05,340 --> 00:00:07,273
Data Structures and Algorithms.
3
00:00:08,370 --> 00:00:12,220
Now, last week we looked at
selection sort, insertion sort,
4
00:00:12,220 --> 00:00:13,119
and we saw our first
5
00:00:13,119 --> 00:00:16,313
O(n log n) sorting algorithm, merge sort.
6
00:00:17,380 --> 00:00:19,850
This week, we'll continue our exploration
7
00:00:19,850 --> 00:00:21,730
of sorting algorithms.
8
00:00:21,730 --> 00:00:24,740
We'll see two more O(n log n) algorithms,
9
00:00:24,740 --> 00:00:26,891
Quicksort and Heapsort.
10
00:00:26,891 --> 00:00:29,910
Quicksort is another divide
and conquer algorithm
11
00:00:29,910 --> 00:00:32,010
that typically outperforms merge sort
12
00:00:32,010 --> 00:00:34,800
in a wide variety of use cases.
13
00:00:34,800 --> 00:00:36,240
The downside of Quicksort
14
00:00:36,240 --> 00:00:38,760
is that it can have a
worst case time complexity
15
00:00:38,760 --> 00:00:40,510
of O(n) squared,
16
00:00:40,510 --> 00:00:43,100
but we'll see how to take
steps to reduce the likelihood
17
00:00:43,100 --> 00:00:44,033
of this occurring.
18
00:00:45,072 --> 00:00:47,960
Now, Heapsort works differently.
19
00:00:47,960 --> 00:00:51,034
Heapsort algorithm makes
use of a binary heap.
20
00:00:51,034 --> 00:00:54,830
Remember binary heaps from week six?
21
00:00:54,830 --> 00:00:57,560
Binary heaps have that
property that the minimum value
22
00:00:57,560 --> 00:01:00,324
is always at the root, if it's a min heap.
23
00:01:00,324 --> 00:01:02,630
Or in the case of a max heap,
24
00:01:02,630 --> 00:01:05,860
it's the maximum value
that's always at the root.
25
00:01:05,860 --> 00:01:08,260
Heapsort takes advantage of this,
26
00:01:08,260 --> 00:01:11,600
storing unsorted values in a binary heap,
27
00:01:11,600 --> 00:01:14,880
and then extracting values
from the root one at a time,
28
00:01:14,880 --> 00:01:17,113
and using these to build a sorted factor.
29
00:01:18,010 --> 00:01:19,670
We'll provide a little refresher,
30
00:01:19,670 --> 00:01:20,630
but if you need to,
31
00:01:20,630 --> 00:01:22,420
go back to the week six material
32
00:01:22,420 --> 00:01:24,653
and refresh your memory on binary heaps.
33
00:01:26,113 --> 00:01:26,946
We'll also look at two
sub (n log n) algorithms,
34
00:01:26,946 --> 00:01:31,940
bucket sort and rated sort.
35
00:01:31,940 --> 00:01:34,590
Now, these aren't the general
purpose sorting algorithms
36
00:01:34,590 --> 00:01:35,644
like the others,
37
00:01:35,644 --> 00:01:39,664
and they must be tailored
to specific use cases.
38
00:01:39,664 --> 00:01:41,860
But, we'll see that when we have data
39
00:01:41,860 --> 00:01:43,680
with certain characteristics,
40
00:01:43,680 --> 00:01:46,380
and we adjust these
algorithms accordingly,
41
00:01:46,380 --> 00:01:48,997
that we can have complexity
of less than O(n log n).
42
00:01:51,240 --> 00:01:53,330
We'll explain how all
these algorithms work
43
00:01:53,330 --> 00:01:55,670
and we'll implement each one in C++,
44
00:01:55,670 --> 00:01:58,081
like we've done in previous weeks.
45
00:01:58,081 --> 00:02:01,000
So, get started with this
week's video lectures
46
00:02:01,000 --> 00:02:02,250
and demonstrations,
47
00:02:02,250 --> 00:02:05,231
and the supplemental materials
posted on Blackboard.
48
00:02:05,231 --> 00:02:07,813
And there's also some
reading in the textbook.
49
00:02:08,860 --> 00:02:11,190
At the end of the week,
we'll have another quiz,
50
00:02:11,190 --> 00:02:12,740
which will cover this week's material
51
00:02:12,740 --> 00:02:15,533
and some material from last week.
52
00:02:15,533 --> 00:02:17,490
And that's all for now.
53
00:02:17,490 --> 00:02:20,920
I'll see you on our yellow
dig discussion board.
54
00:02:20,920 --> 00:02:22,070
Good luck and have fun.