Bogosort5:39 with Jay McGavren
To help make clear the importance of choosing a good sorting algorithm, we're going to start with a bad one. It's called "Bogosort".
See the instruction step that follows this video; we'll have details on the code there!
Our end goal is to sort a list of names. 0:00 But comparing numbers is a little easier than comparing strings. 0:02 So we're going to start by sorting a list of numbers. 0:05 I'll show you how to modify our examples to sort strings at the end of the course. 0:09 To help make clear the importance of choosing a good sorting algorithm, 0:13 we're going to start with a bad one. 0:17 It's called bogo_sort. 0:19 Basically, bogo_sort just randomizes the order of the list repeatedly 0:21 until it's sorted. 0:26 Here's a Python code file where we're going to implement bogo_sort. 0:27 It's not important to understand this code here at the top. 0:31 Although, we'll have info on it in the teacher's notes, if you really want it. 0:34 All you need to know is that it takes the name of a file that we pass on the command 0:37 line, loads it, and returns a Python list. 0:41 Which is just like an array in other languages, 0:44 containing all the numbers that it read from the file. 0:47 Let me have the program print out the list of numbers it loads so you can see it. 0:50 We'll call the print method, and we'll pass it the list of numbers. 0:54 Save that, let's run it real quick with, python bogo_sort.py. 0:59 Whoops. 1:07 And we need to provide it the name of the file here on the command line that we're 1:07 gonna load. 1:12 So it's in the numbers directory. 1:13 A slash separates the directory name from the file name, 5.txt. 1:16 And there's our list of numbers that was loaded from the file. 1:22 Okay, let me delete that print statement and then we'll move on. 1:25 bogo_sort just randomly rearranges the list of values over and over. 1:29 So the first thing we're going to need is a function to detect when the list is 1:33 sorted. 1:38 We'll write an is_sorted function that takes a list of values as a parameter. 1:38 It will return true if the list passed in as sorted or false if it isn't. 1:46 We'll loop through the numeric index of each value in the list, 1:51 from 0 to 1 less than the length of the list. 1:55 Like many languages, Python list indexes begin at 0, 1:57 so a list with a length of 5 has indexes going from 0 through 4. 2:00 If the list is sorted, 2:06 then every value in it will be less than the one that comes after it. 2:07 So we test to see whether the current item is greater than the one that follows it. 2:11 If it is, it means the whole list is not sorted so we can return false. 2:16 If we get down here, 2:21 it means the loop completed without finding any unsorted values. 2:22 Python uses whitespace to mark code blocks, so 2:26 unindenting the code like this marks the end of the loop. 2:29 Since all the values are sorted, we can return True. 2:32 Now we need to write the function that will actually do the so-called sorting. 2:36 The bogo_sort function will also take a list of values it's working with as 2:40 a parameter. 2:44 We'll call our is_sorted function to test whether the list is sorted. 2:45 We'll keep looping until is_sorted returns true. 2:49 Python has a ready-made function that randomizes the order of elements in 2:53 the list. 2:57 Since the list isn't sorted, we'll call that function here. 2:57 And since this is inside the loop, it'll be randomized over and 3:01 over until our is_sorted function returns True. 3:04 If the loop exits, it means is_sorted returned True and the list is sorted. 3:08 So we can now return the sorted list. 3:12 Finally, we need to call our bogo_sort function, 3:15 pass it the list we loaded from the file and print the sorted list it returns. 3:18 Okay, let's save this and try running it. 3:24 Do so with, python, the name of the script, bogus_sort.py, and 3:26 the name of the file we're going to run it on, numbers directory, 5.txt. 3:31 It looks like it's sorting our list successfully. 3:39 But how efficient is this? 3:42 Let's add some code to track the number of times it attempts to sort the list. 3:44 Up here at the top of the bogo_sort function, 3:48 we'll add a variable to track the number of attempts it's made. 3:50 We'll name it attempts and we'll set its initial value to 0, 3:53 since we haven't made any attempts yet. 3:56 With each pass through the loop, we'll print current number of attempts. 4:00 And then here at the loop, after attempting to shuffle the values, 4:05 we'll add one to the account of attempts. 4:08 Let's save this and let's try running it again a couple times. 4:14 In the console, 4:18 I can just press the up arrow to bring up the previous commands and re-run. 4:19 So it looks like this first run to sort this five element list took 363 attempts. 4:24 Let's try it again. 4:29 This time it only took 91 attempts. 4:31 We're simply randomizing the list with each attempt so 4:34 each run of the program takes a random number of attempts. 4:37 Now let's try the same program with a larger number of items, python 4:42 bogo_sort numbers. 4:46 I have a list of 8 items set up here in this other file. 4:51 This time it takes 11,000 attempts. 4:57 Only 487 this time. 5:01 And this time 13,000. 5:06 You can see that the trend is increasing steadily. 5:07 The problem with bogo_sort is that it doesn't make any progress 5:11 toward a solution with each pass. 5:14 It could generate a list where just one value was out of order, but 5:16 then on the next attempt it could generate a list where all the elements 5:20 are out of order again. 5:23 Stumbling on a solution is literally a matter of luck. 5:25 And for lists with more than a few items, it might never happen. 5:28 Up next, we'll look at selection_sort. 5:32 It's a sorting algorithm that's still slow, but it's better than bogo_sort. 5:35
You need to sign up for Treehouse in order to download course files.Sign up