1 00:00:01,360 --> 00:00:02,320 - Hey there. 2 00:00:02,320 --> 00:00:06,190 Welcome to week seven of CS124 online, 3 00:00:06,190 --> 00:00:08,253 Data Structures and Algorithms. 4 00:00:09,550 --> 00:00:10,410 Well, let's see. 5 00:00:10,410 --> 00:00:14,230 Last week we studied binary heaps and priority queues 6 00:00:14,230 --> 00:00:17,050 and we started our study of sorting algorithms 7 00:00:17,050 --> 00:00:17,933 with bubble sort. 8 00:00:18,920 --> 00:00:22,060 And this week and next we'll continue our tour 9 00:00:22,060 --> 00:00:23,260 of sorting algorithms. 10 00:00:23,260 --> 00:00:24,963 We have a lot to go over. 11 00:00:26,190 --> 00:00:28,930 So last week we saw the bubble sort was effective, 12 00:00:28,930 --> 00:00:33,080 that is, it works, but that it's not very efficient. 13 00:00:33,080 --> 00:00:35,710 And this week we'll see some similar algorithms, 14 00:00:35,710 --> 00:00:38,200 algorithms that work by swapping elements, 15 00:00:38,200 --> 00:00:40,980 that yield better performance than bubble sort. 16 00:00:40,980 --> 00:00:43,763 These are selection sort and insertion sort. 17 00:00:45,090 --> 00:00:46,310 Selection sort works 18 00:00:46,310 --> 00:00:49,000 by scanning the unsorted portion of the vector, 19 00:00:49,000 --> 00:00:50,480 finds the minimum value, 20 00:00:50,480 --> 00:00:54,110 and then swaps it with the left-most unsorted element. 21 00:00:54,110 --> 00:00:57,390 And in this way, it performs the smallest number of swaps. 22 00:00:57,390 --> 00:00:58,990 That's what it's designed to do, 23 00:00:58,990 --> 00:01:01,850 to perform the smallest number of swaps. 24 00:01:01,850 --> 00:01:04,060 And that's where it gets its performance improvement 25 00:01:04,060 --> 00:01:05,043 over bubble sort. 26 00:01:06,360 --> 00:01:08,930 Now, whereas selection sort is designed to 27 00:01:08,930 --> 00:01:11,250 perform the smallest number of swaps, 28 00:01:11,250 --> 00:01:13,740 insertion sort is designed to work 29 00:01:13,740 --> 00:01:16,830 with only one unsorted element at a time, 30 00:01:16,830 --> 00:01:18,850 thus reducing the number of comparisons 31 00:01:18,850 --> 00:01:19,973 that need to be made. 32 00:01:21,550 --> 00:01:24,030 Finally, we'll learn about merge sort. 33 00:01:24,030 --> 00:01:27,040 Now merge sort is a completely different kind of algorithm 34 00:01:27,040 --> 00:01:28,820 than we've seen before. 35 00:01:28,820 --> 00:01:31,730 It's a divide and conquer algorithm. 36 00:01:31,730 --> 00:01:33,890 And divide and conquer algorithms work 37 00:01:33,890 --> 00:01:37,830 by dividing the problem instance into smaller problems, 38 00:01:37,830 --> 00:01:39,950 solving the smaller problems, 39 00:01:39,950 --> 00:01:42,830 and then constructing a result by combining, 40 00:01:42,830 --> 00:01:45,930 in one way or another depending on the algorithm, 41 00:01:45,930 --> 00:01:48,953 combining those results to produce a complete solution. 42 00:01:50,000 --> 00:01:52,790 A merge sort is much faster than bubble sort, 43 00:01:52,790 --> 00:01:55,160 selection sort, or insertion sort. 44 00:01:55,160 --> 00:01:57,633 Its time complexity is O of nLogn. 45 00:01:59,340 --> 00:02:01,620 We'll explain how all these algorithms work 46 00:02:01,620 --> 00:02:04,960 and we'll implement each one in C++. 47 00:02:04,960 --> 00:02:05,810 So get started 48 00:02:05,810 --> 00:02:08,840 with this week's video lectures and demonstrations 49 00:02:08,840 --> 00:02:11,780 and the supplemental materials posted on Blackboard. 50 00:02:11,780 --> 00:02:14,850 And don't forget the assigned reading in the textbook. 51 00:02:14,850 --> 00:02:17,140 At the end of this week, like all the other weeks, 52 00:02:17,140 --> 00:02:20,370 we'll have another quiz that'll cover this week's material 53 00:02:20,370 --> 00:02:23,570 and some additional material that we covered last week. 54 00:02:23,570 --> 00:02:27,330 So you should expect something on binary heaps 55 00:02:27,330 --> 00:02:30,650 and all four sorting algorithms 56 00:02:30,650 --> 00:02:32,900 that we'll have seen by the end of this week. 57 00:02:33,890 --> 00:02:35,560 So that's all for now. 58 00:02:35,560 --> 00:02:38,170 I'll see you on our Yellowdig discussion board 59 00:02:38,170 --> 00:02:39,983 and have fun.