Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll

Algorithms: Sorting and Searching

Well done!

You have completed Algorithms: Sorting and Searching!

Sign up for Treehouse Back to Library
Preview
Video Player
00:00
00:00
00:00
  1. 2x 2x
  2. 1.75x 1.75x
  3. 1.5x 1.5x
  4. 1.25x 1.25x
  5. 1.1x 1.1x
  6. 1x 1x
  7. 0.75x 0.75x
  8. 0.5x 0.5x
Use Up/Down Arrow keys to increase or decrease volume.

Actual Run Time for Sorting Algorithms

2:13 with Jay McGavren

Let's compare how long Selection Sort, Quicksort, and Merge Sort take to run on different data sets.

I've removed the call to print that displays the sorted list at the end of our 0:00
selection_sort, quicksort, and merge_sort scripts. 0:04
That way, it'll still run the sort, but 0:07
the output won't get in the way of our comparing run times. 0:09
Let's try running each of these scripts, and see how long it takes. 0:13
time python selection_sort, we'll do that 0:17
one first, numbers/10,000.txt. 0:22
We combine the user and sys results, and that gives us about 6 seconds. 0:30
Now let's try quicksort, time python 0:35
quicksort.py numbers/10000.txt. 0:40
Much faster, less than a second. 0:45
And finally, time python merge_sort.py numbers/10000.txt. 0:48
A little longer, but far less than a second. 0:58
So even on a list with just 10,000 numbers, 1:01
selection_sort takes many times as long as quicksort and merge_sort. 1:04
And remember, I ran the selection_sort script on a file with a million numbers. 1:09
And it took so long that my workspace timed out before it completed. 1:13
It looks like selection_sort is out of the running as a viable sorting algorithm. 1:18
It may be easy to understand and implement, but 1:22
it's just too slow to handle the huge data sets that are out in the real world. 1:25
Now let's try quicksort and merge_sort on our file with a million numbers, and 1:31
see how they compare there. 1:35
time python quicksort.py 1:36
numbers/1000000.txt. 1:40
Looks like it took about 11 seconds of CPU time. 1:49
Now let's try merge_sort, time python 1:53
merge_sort.py numbers/1000000.txt. 1:57
That took about 15 seconds of CPU time. 2:05
It looks like quicksort is marginally faster than merge_sort on this 2:08
sample data. 2:12