1
00:00:08,864 --> 00:00:11,660
Congratulations, now you
really know how to sort.

2
00:00:11,660 --> 00:00:15,540
Simple sorts, complex sorts,
all sorts of sorts.

3
00:00:15,540 --> 00:00:19,870
You can sort dictionary keys based
on some property of their values.

4
00:00:19,870 --> 00:00:23,690
You can break ties by having
the key function return a tuple.

5
00:00:23,690 --> 00:00:26,910
You can use lambda expressions,
you can use name functions,

6
00:00:26,910 --> 00:00:28,280
you are a pro at sorting.

7
00:00:29,870 --> 00:00:33,390
Now in the intro to this week, I made a
big deal out of saying, we're not going to

8
00:00:33,390 --> 00:00:37,690
go into details of which sorting algorithm
gets used and how long it takes it to run.

9
00:00:38,850 --> 00:00:42,740
So instead of a straight up joke, let me
give you a little programmer's humor.

10
00:00:42,740 --> 00:00:45,840
A sorting algorithm that
runs really slowly.

11
00:00:47,490 --> 00:00:51,610
It's called bogosort, and
it works by trial and error.

12
00:00:51,610 --> 00:00:55,820
Take the items, shuffle them,
just at random into some random order, and

13
00:00:55,820 --> 00:00:58,050
check if they happen to be sorted.

14
00:00:58,050 --> 00:00:59,600
If they are, we're done.

15
00:00:59,600 --> 00:01:00,850
Otherwise, try again.

16
00:01:00,850 --> 00:01:03,030
Shuffle, see if they're sorted.

17
00:01:03,030 --> 00:01:04,649
Keep going until you get a lucky shuffle.

18
00:01:06,990 --> 00:01:10,160
Remarkably, the code for
this in Python is short.

19
00:01:10,160 --> 00:01:13,930
In the random module, there's
a built-in function called shuffle, and

20
00:01:13,930 --> 00:01:17,880
I wrote the function to check if
a list is in order in five lines, and

21
00:01:17,880 --> 00:01:20,480
another four for the trial and
error wild loop.

22
00:01:20,480 --> 00:01:21,500
But here's the full code.

23
00:01:23,670 --> 00:01:27,920
Of course, because you do a random shuffle
every time, it takes a random amount of

24
00:01:27,920 --> 00:01:32,960
time to finish, but as you can imagine,
this is not a fast way to do sorting.

25
00:01:32,960 --> 00:01:34,080
You got a bunch of items and

26
00:01:34,080 --> 00:01:38,080
you just shuffle them, the chances that
it's going to be sorted aren't very good.

27
00:01:38,080 --> 00:01:42,830
I just ran it once on a list of ten items
and it took 68 seconds to complete.

28
00:01:42,830 --> 00:01:44,610
I didn't dare to try it with 11 items.

29
00:01:45,856 --> 00:01:49,593
By contrast, Python's built-in
sorted function was able to

30
00:01:49,593 --> 00:01:52,421
sort a million items in
just over half a second.

31
00:01:54,879 --> 00:01:56,830
Now you have a party trick.

32
00:01:56,830 --> 00:02:00,920
Ask your friends who've taken some
computer science courses some time ago

33
00:02:00,920 --> 00:02:03,590
to try to remember the slowest
sorting algorithm they studied.

34
00:02:04,600 --> 00:02:07,700
They'll have fun recalling bubble sort and
insertion sort and

35
00:02:07,700 --> 00:02:12,580
trying to decide which one is slower, and
then you can regale them with bogosort.

36
00:02:12,580 --> 00:02:14,460
You'll be the life of the party, trust me.

37
00:02:16,250 --> 00:02:16,870
See you next time.