1 00:00:00,310 --> 00:00:01,610 You have seen bogo_sort. 2 00:00:01,610 --> 00:00:05,280 Which doesn't make any progress toward sorting a list with each pass, 3 00:00:05,280 --> 00:00:07,348 either it's entirely sorted or it isn't. 4 00:00:07,348 --> 00:00:11,880 You've seen selection_sort, which moves one value over to an a sorted 5 00:00:11,880 --> 00:00:15,410 list with each pass so that it has fewer items to compare each time. 6 00:00:16,460 --> 00:00:20,700 Now let's look at an algorithm that speeds up the process further by further reducing 7 00:00:20,700 --> 00:00:22,630 the number of comparison it makes. 8 00:00:22,630 --> 00:00:24,790 It's called quicksort. 9 00:00:24,790 --> 00:00:27,890 Here's some Python code where we'll implement quicksort. 10 00:00:27,890 --> 00:00:30,370 Again, you can ignore these lines at the top. 11 00:00:30,370 --> 00:00:34,410 We're just using them to load a file full of numbers into a list. 12 00:00:34,410 --> 00:00:37,120 The quicksort algorithm relies on recursion. 13 00:00:37,120 --> 00:00:39,940 To implement, it we'll write a recursive function. 14 00:00:39,940 --> 00:00:43,495 We'll accept the list of numbers to sort as a parameter. 15 00:00:43,495 --> 00:00:47,070 quicksort is recursive because it keeps calling itself with smaller and 16 00:00:47,070 --> 00:00:50,070 smaller subsets of the list you're trying to sort. 17 00:00:50,070 --> 00:00:53,250 We're going to need a base case where the recursion stops, so 18 00:00:53,250 --> 00:00:55,880 it doesn't end in an infinite loop. 19 00:00:55,880 --> 00:00:58,550 Lists that are empty don't need to be sorted, and 20 00:00:58,550 --> 00:01:01,640 lists with just one element don't need to be sorted either. 21 00:01:01,640 --> 00:01:04,420 In both cases, there's nothing to flip around. 22 00:01:04,420 --> 00:01:06,240 So we'll make that our base case. 23 00:01:06,240 --> 00:01:10,302 If there are 0 or 1 elements in the list past to the quicksort function, 24 00:01:10,302 --> 00:01:13,900 we'll return the unaltered list to the caller. 25 00:01:13,900 --> 00:01:19,429 Lastly, we need to call our quicksort function with our list of numbers and 26 00:01:19,429 --> 00:01:21,463 print the list it returns. 27 00:01:23,399 --> 00:01:27,709 That takes care of our base case, now we need a recursive case. 28 00:01:27,709 --> 00:01:30,327 We're going to rely on a technique that's common 29 00:01:30,327 --> 00:01:32,894 in algorithm design called divide and conquer. 30 00:01:32,894 --> 00:01:36,749 Basically, we're going to take our problem and split it into smaller and 31 00:01:36,749 --> 00:01:39,313 smaller problems until they're easy to solve. 32 00:01:39,313 --> 00:01:44,270 In this case, that means taking our list and splitting it into smaller lists. 33 00:01:44,270 --> 00:01:48,315 Viewers, a suggestion, the process I'm about to describe is complex. 34 00:01:48,315 --> 00:01:50,212 There's just no way around it. 35 00:01:50,212 --> 00:01:54,280 If you're having trouble following along, remember the video playback controls. 36 00:01:54,280 --> 00:01:58,720 Feel free to slow the playback down, rewind or pause the video as needed. 37 00:01:58,720 --> 00:02:03,058 After you watch this the first time, you may also find it helpful to rewind and 38 00:02:03,058 --> 00:02:05,615 make your own diagram of the process as we go. 39 00:02:05,615 --> 00:02:07,610 Okay, ready, here it goes. 40 00:02:08,970 --> 00:02:13,270 Suppose we load the numbers from our 8.txt file into a list. 41 00:02:13,270 --> 00:02:14,990 How do we divide it? 42 00:02:14,990 --> 00:02:17,680 It would probably be smart to have our quicksort function 43 00:02:17,680 --> 00:02:21,410 divide the list in a way that brings it closer to being sorted. 44 00:02:21,410 --> 00:02:23,294 Let us pick an item from the list. 45 00:02:23,294 --> 00:02:26,405 We'll just pick the first item for now, 4. 46 00:02:26,405 --> 00:02:29,073 We'll call this value we've picked the pivot, 47 00:02:29,073 --> 00:02:31,489 wike the center of a seesaw on a playground. 48 00:02:31,489 --> 00:02:33,672 We'll break the list into two sublists. 49 00:02:33,672 --> 00:02:36,920 The first sublist will contain all the items in the original list that 50 00:02:36,920 --> 00:02:38,265 are smaller than the pivot. 51 00:02:38,265 --> 00:02:41,754 The second sublist will contain all the items in the original list 52 00:02:41,754 --> 00:02:43,537 that are greater than the pivot. 53 00:02:43,537 --> 00:02:48,250 The sublist of values less than and greater than the pivot aren't sorted. 54 00:02:48,250 --> 00:02:49,950 But what if they were? 55 00:02:49,950 --> 00:02:53,760 You could just join the sublists and the pivot all together into one list, and 56 00:02:53,760 --> 00:02:56,040 the whole thing would be sorted. 57 00:02:56,040 --> 00:02:57,840 So how do we sort the sublist? 58 00:02:57,840 --> 00:03:00,700 We call our quicksort function recursively on them. 59 00:03:00,700 --> 00:03:03,270 This may seem like magic, but it's not. 60 00:03:03,270 --> 00:03:07,220 It's the divide and conquer algorithm technique at work. 61 00:03:07,220 --> 00:03:09,620 If our quicksort function works on the big list, 62 00:03:09,620 --> 00:03:11,460 then it will work on the smaller list, too. 63 00:03:12,800 --> 00:03:16,620 For our first sublist, we take the first item, it's the pivot again. 64 00:03:16,620 --> 00:03:18,242 That's 3. 65 00:03:18,242 --> 00:03:20,970 We break the sublist into two sublists. 66 00:03:20,970 --> 00:03:22,400 One with everything less than the pivot. 67 00:03:22,400 --> 00:03:25,280 And one with everything greater than the pivot. 68 00:03:25,280 --> 00:03:28,240 Notice that there's a value equal to the pivot that gets put in to 69 00:03:28,240 --> 00:03:30,000 the less than sublist. 70 00:03:30,000 --> 00:03:33,160 Our finished quicksort function is actually going to put everything that's 71 00:03:33,160 --> 00:03:36,890 less than or equal to the pivot in the first sublist. 72 00:03:36,890 --> 00:03:40,020 But I don't wanna say less than or equal to over and over, so 73 00:03:40,020 --> 00:03:42,980 I'm just referring to it as the less than pivot sublist. 74 00:03:44,160 --> 00:03:47,290 Also, notice that there are no values greater than the pivot. 75 00:03:47,290 --> 00:03:48,030 That’s okay. 76 00:03:48,030 --> 00:03:49,930 When we join the sublists back together, 77 00:03:49,930 --> 00:03:52,730 that just means nothing will be in the returned list after the pivot. 78 00:03:53,900 --> 00:03:56,870 We still have one sublist that’s more than one element long. 79 00:03:56,870 --> 00:03:59,700 So we call our quicksort function on that too. 80 00:03:59,700 --> 00:04:01,700 You and I can see that it’s already sorted. 81 00:04:01,700 --> 00:04:05,350 But the computer doesn’t know that, so it’ll call it anyway, just in case. 82 00:04:06,410 --> 00:04:08,678 It picks the first element, 2, as a pivot. 83 00:04:08,678 --> 00:04:10,624 There are no elements less than the pivot and 84 00:04:10,624 --> 00:04:12,470 only one element greater than the pivot. 85 00:04:13,690 --> 00:04:15,250 That's it for the recursive case. 86 00:04:15,250 --> 00:04:18,400 We've finally hit the base case for our quicksort function. 87 00:04:18,400 --> 00:04:21,832 It'll be called on both the empty list of elements less than the pivot and 88 00:04:21,832 --> 00:04:24,377 the one item list of elements greater than the pivot. 89 00:04:24,377 --> 00:04:27,326 But both of these lists will be returned as they are, 90 00:04:27,326 --> 00:04:29,348 because there's nothing to sort. 91 00:04:29,348 --> 00:04:31,981 So now, at the level of the call stack above this, 92 00:04:31,981 --> 00:04:36,061 the return sorted lists are used in place of the unsorted sublist that's less 93 00:04:36,061 --> 00:04:39,908 than the pivot and the unsorted sublist that's greater than the pivot. 94 00:04:39,908 --> 00:04:42,592 These are joined together into one sorted list. 95 00:04:42,592 --> 00:04:46,030 Remember that any empty lists get discarded. 96 00:04:46,030 --> 00:04:48,370 Then at the level of the call stack above that, 97 00:04:48,370 --> 00:04:52,230 the returned sorted lists are used in place of the unsorted sublists there. 98 00:04:52,230 --> 00:04:54,375 Again, they were already sorted, but 99 00:04:54,375 --> 00:04:57,828 the quicksort method was called on them anyway, just in case. 100 00:04:57,828 --> 00:05:01,219 The sublists are joined together into one sorted list. 101 00:05:01,219 --> 00:05:04,472 At the level of the call stack above that, the return sorted list 102 00:05:04,472 --> 00:05:07,977 is used in place of the unsorted sublist that's less that the pivot. 103 00:05:07,977 --> 00:05:11,947 So now everything that's less than or equal to the pivot is sorted. 104 00:05:11,947 --> 00:05:16,570 Now we call quicksort on the unsorted sublist that's greater than the pivot and 105 00:05:16,570 --> 00:05:18,853 the process repeats for that sublist. 106 00:05:18,853 --> 00:05:21,502 We pick the first element, 6, as the pivot. 107 00:05:21,502 --> 00:05:24,665 We split the sublist into sublists of elements that are less than and 108 00:05:24,665 --> 00:05:25,896 greater than this pivot. 109 00:05:25,896 --> 00:05:31,087 And we recursively call the quicksort function until those sublists are sorted. 110 00:05:31,087 --> 00:05:35,270 Eventually, a sorted sublists is returned to our first quicksort function call. 111 00:05:35,270 --> 00:05:39,252 We combine the sublist that's less-than-or-equal-to the pivot, 112 00:05:39,252 --> 00:05:43,962 the pivot itself, and the sublist that's greater than the pivot into a single list. 113 00:05:43,962 --> 00:05:48,521 And because we recursively sorted the sublist, the whole list is sorted. 114 00:05:48,521 --> 00:05:51,216 So that's how the quicksort function is going to work. 115 00:05:51,216 --> 00:05:54,217 In the next video, we'll show you the actual code.