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.