1 00:00:00,000 --> 00:00:02,556 Quick sort works by picking a pivot value, 2 00:00:02,556 --> 00:00:05,616 then splitting the full list into two sub-lists. 3 00:00:05,616 --> 00:00:09,302 The first sub-list has all the values less than or equal to the pivot and 4 00:00:09,302 --> 00:00:12,638 the second sub-list has all the values greater than the pivot. 5 00:00:12,638 --> 00:00:16,628 The quick sort function recursively calls itself to sort these sub-lists and 6 00:00:16,628 --> 00:00:20,629 then to sort the sub-lists of those sub-lists until the full list is sorted. 7 00:00:21,830 --> 00:00:24,090 Now it's time to actually implement this in code. 8 00:00:25,210 --> 00:00:29,790 We already have the base case written, any list passed in that consists of zero or 9 00:00:29,790 --> 00:00:34,150 one values will be returned as is because there's nothing to sort. 10 00:00:34,150 --> 00:00:38,630 Now we need to create a list that will hold all the values less than the pivot, 11 00:00:38,630 --> 00:00:41,570 that list will be empty at first, we do the same for 12 00:00:41,570 --> 00:00:43,467 values greater than the pivot. 13 00:00:43,467 --> 00:00:45,640 Next we need to choose the pivot value. 14 00:00:45,640 --> 00:00:48,970 For now, we just grab the first item from the list, 15 00:00:48,970 --> 00:00:53,315 then we loop through all the items in the list following the pivot. 16 00:00:53,315 --> 00:00:57,895 We check to see whether the current value is less than or equal to the pivot, 17 00:00:57,895 --> 00:01:01,692 if it is, we copy it to the sublist values less than the pivot. 18 00:01:03,724 --> 00:01:07,348 Otherwise the current value must be greater than the pivot so 19 00:01:07,348 --> 00:01:09,061 we copy it to the other list. 20 00:01:13,962 --> 00:01:17,055 This last line is where the recursive magic happens, 21 00:01:17,055 --> 00:01:21,396 we call quick sort recursively on the sub list that's less than the pivot. 22 00:01:21,396 --> 00:01:24,654 We do the same for the sublist that's greater than the pivot. 23 00:01:24,654 --> 00:01:29,621 Those two culls will return sorted lists, so we combine the sorted values list 24 00:01:29,621 --> 00:01:34,663 in the pivot, the pivot itself, and the sorted values greater than the pivot, 25 00:01:34,663 --> 00:01:38,070 that gives us a complete sorted list which we return. 26 00:01:38,070 --> 00:01:40,734 This took a lot of prep work, are you ready? 27 00:01:40,734 --> 00:01:44,731 Let's try running it, python, 28 00:01:44,731 --> 00:01:49,312 quicksort.py numbers/8.text. 29 00:01:49,312 --> 00:01:52,398 It outputs our sorted list, I don't know about you, 30 00:01:52,398 --> 00:01:55,838 but this whole thing still seems a little too magical to me. 31 00:01:55,838 --> 00:02:00,119 Let's add a couple print statements to the program so we can see what it's doing. 32 00:02:00,119 --> 00:02:03,869 First, we'll add a print statement right before the first call to the quicksort 33 00:02:03,869 --> 00:02:06,850 function, so we can see the unsorted list. 34 00:02:06,850 --> 00:02:09,620 We'll also add a print right within the quick sort function, 35 00:02:09,620 --> 00:02:11,720 right before the recursive calls. 36 00:02:11,720 --> 00:02:15,555 Again, this string format encode is just to keep the info aligned in columns. 37 00:02:25,471 --> 00:02:30,550 Let's try running this again and now you can see our new debug output. 38 00:02:30,550 --> 00:02:35,089 Each time quick sort goes to call itself aposabli, it prints out the pivot as well 39 00:02:35,089 --> 00:02:38,823 as the sub list of items less than or equal to the pivot, if any, and 40 00:02:38,823 --> 00:02:41,863 the sub list of items greater than the pivot, if any. 41 00:02:41,863 --> 00:02:46,946 You can see that first it sorts the sub list of items less than the pivot at 42 00:02:46,946 --> 00:02:52,057 the top level, it goes through a couple levels of recursion to do that. 43 00:02:52,057 --> 00:02:54,998 There are actually additional levels of recursion, but 44 00:02:54,998 --> 00:02:58,733 they're from calls to quicksort with a list of zero or one elements, and 45 00:02:58,733 --> 00:03:01,809 those calls return before the print statement is reached. 46 00:03:01,809 --> 00:03:06,460 Then it starts sorting the second sublist from the top level with items greater than 47 00:03:06,460 --> 00:03:11,930 the original pivot, you can see a couple levels of recursion for that sort as well. 48 00:03:11,930 --> 00:03:16,320 Finally, when both sublets are recursively sorted, the original call to the quicksort 49 00:03:16,320 --> 00:03:19,930 function returns, and we get the sorted list back. 50 00:03:19,930 --> 00:03:23,870 So we know that it works, the next question is how well does it work? 51 00:03:23,870 --> 00:03:28,280 Let's go back to our file of 10,000 numbers and see if it can sort those. 52 00:03:28,280 --> 00:03:31,310 First though, I'm going to remove our two debug calls to print, so 53 00:03:31,310 --> 00:03:33,080 it doesn't produce unreadable output. 54 00:03:34,680 --> 00:03:38,540 A quick note, if you try running this on a file with a lot of repeated values, 55 00:03:38,540 --> 00:03:43,380 it's possible you'll get a run time error of maximum recursion depth exceeded. 56 00:03:43,380 --> 00:03:46,530 If you do, see the teacher's notes for a possible solution. 57 00:03:48,240 --> 00:03:52,098 Now let's try running our quicksort program against the 10000 dot text file. 58 00:03:52,098 --> 00:03:59,910 Python quicksort.py numbers/10000.txt. 59 00:03:59,910 --> 00:04:04,080 There we go and it seems pretty fast, but how fast exactly? 60 00:04:04,080 --> 00:04:06,740 Let's run it with the time command to see how long it takes. 61 00:04:06,740 --> 00:04:10,988 Time python quicksort.py 62 00:04:10,988 --> 00:04:15,920 numbers/10000.txt. 63 00:04:15,920 --> 00:04:21,140 Remember we need to ignore the real result, and add the user and sys results, 64 00:04:21,140 --> 00:04:26,490 it took less than a second of CPU time to sort 10,000 numbers with quick sort. 65 00:04:26,490 --> 00:04:30,100 Remember that selection sort took about 13 seconds. 66 00:04:30,100 --> 00:04:33,978 That's a pretty substantial improvement and with a million numbers, 67 00:04:33,978 --> 00:04:37,867 selection sort took so long that it never even finished successfully. 68 00:04:37,867 --> 00:04:42,822 Let's see if quicksort performs any better, 69 00:04:42,822 --> 00:04:49,564 time python quicksort.pi numbers/1000000.txt. 70 00:04:55,971 --> 00:04:59,872 Not only did quick sort sort a million numbers successfully, 71 00:04:59,872 --> 00:05:02,656 it only took about 11 seconds of CPU time. 72 00:05:02,656 --> 00:05:07,459 Quicksort is clearly much, much faster than selection sort, how much faster? 73 00:05:07,459 --> 00:05:10,194 That's something we'll discuss in a later video. 74 00:05:10,194 --> 00:05:14,006 What we've shown you here is just one way they implement quick sort. 75 00:05:14,006 --> 00:05:17,977 Although the basic algorithm is always the same, the details can vary, 76 00:05:17,977 --> 00:05:19,552 like how you pick the pivot. 77 00:05:19,552 --> 00:05:22,516 See the teacher's notes for more details.