- Sorting and Searching 3:55
- Bogosort 5:39
- Code for Bogosort
- Selection Sort 6:35
- Code for Selection Sort
- Getting the Run Time of a Program 4:06
- Recursion 10:00
- Quicksort 5:54
- Implementing Quicksort 5:22
- Code for Quicksort
- Merge Sort 7:10
- Code for Merge Sort
- Actual Run Time for Sorting Algorithms 2:13
- Big-O Run Times of Sorting Algorithms 5:42
- Sorting Algorithms 11 questions
Preview
Video Player
00:00
00:00
Bogosort
5:39To help make clear the importance of choosing a good sorting algorithm, we're going to start with a bad one. It's called "Bogosort".
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