1 00:00:00,087 --> 00:00:04,139 I've removed the call to print that displays the sorted list at the end of our 2 00:00:04,139 --> 00:00:07,389 selection_sort, quicksort, and merge_sort scripts. 3 00:00:07,389 --> 00:00:09,889 That way, it'll still run the sort, but 4 00:00:09,889 --> 00:00:13,468 the output won't get in the way of our comparing run times. 5 00:00:13,468 --> 00:00:17,194 Let's try running each of these scripts, and see how long it takes. 6 00:00:17,194 --> 00:00:22,081 time python selection_sort, we'll do that 7 00:00:22,081 --> 00:00:26,851 one first, numbers/10,000.txt. 8 00:00:30,275 --> 00:00:35,850 We combine the user and sys results, and that gives us about 6 seconds. 9 00:00:35,850 --> 00:00:40,244 Now let's try quicksort, time python 10 00:00:40,244 --> 00:00:45,445 quicksort.py numbers/10000.txt. 11 00:00:45,445 --> 00:00:48,182 Much faster, less than a second. 12 00:00:48,182 --> 00:00:56,324 And finally, time python merge_sort.py numbers/10000.txt. 13 00:00:58,656 --> 00:01:01,980 A little longer, but far less than a second. 14 00:01:01,980 --> 00:01:04,623 So even on a list with just 10,000 numbers, 15 00:01:04,623 --> 00:01:08,245 selection_sort takes many times as long as quicksort and merge_sort. 16 00:01:09,780 --> 00:01:13,670 And remember, I ran the selection_sort script on a file with a million numbers. 17 00:01:13,670 --> 00:01:18,150 And it took so long that my workspace timed out before it completed. 18 00:01:18,150 --> 00:01:22,670 It looks like selection_sort is out of the running as a viable sorting algorithm. 19 00:01:22,670 --> 00:01:25,140 It may be easy to understand and implement, but 20 00:01:25,140 --> 00:01:29,170 it's just too slow to handle the huge data sets that are out in the real world. 21 00:01:31,116 --> 00:01:35,012 Now let's try quicksort and merge_sort on our file with a million numbers, and 22 00:01:35,012 --> 00:01:36,396 see how they compare there. 23 00:01:36,396 --> 00:01:40,433 time python quicksort.py 24 00:01:40,433 --> 00:01:45,701 numbers/1000000.txt. 25 00:01:49,468 --> 00:01:53,040 Looks like it took about 11 seconds of CPU time. 26 00:01:53,040 --> 00:01:57,299 Now let's try merge_sort, time python 27 00:01:57,299 --> 00:02:02,785 merge_sort.py numbers/1000000.txt. 28 00:02:05,374 --> 00:02:08,554 That took about 15 seconds of CPU time. 29 00:02:08,554 --> 00:02:12,724 It looks like quicksort is marginally faster than merge_sort on this 30 00:02:12,724 --> 00:02:13,579 sample data.