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.