Week 11: Sorting and Efficiency

Sorting is something intuitive for most people, we make quick comparisons to decide the placement of an item and sometimes even identify the largest (or smallest) items and put them in the "right" spot. Computers are most certainly more efficient than the average human mind when it comes to sorting very large arrays, but it's not intuitive - they need more specific, systematic instructions. However, some "instructions" (sorting algorithms) are certainly more efficient than others.

Some of the sorts we've encountered are:

•  selection sort - find the smallest item in the unsorted portion of the array and place it in its final spot
•  insertion sort - go through the list item by item, placing each item into its right spot relative to the already sorted items
•  bubblesort - go through the list comparing and swapping adjacent items as needed and repeatedly do this until the list is sorted 
• quicksort - choose a pivot and split the list into two; items smaller than the pivot (left) and items larger than the pivot (right) and then recursively call quicksort on both and then join the sorted left, pivot and sorted right.
• mergesort - split the list into two, sort each and then merge the two sorted lists

Generally, the first three tend to take the longest run time on lists which we can see by looking at the methods that are employed. For example, bubblesort looks at each item in the list multiple times before the entire array is sorted. So it's believable that bubblesort has O(n²) time. (Imagine how long that takes for n large!) The last two employ "divide and conquer" methods which are much more efficient when sorting. Mergesort and quicksort have O(nlogn) run time (the exception is the worst case of quicksort which has O(n²) time) which is much faster than O(n²) time. So quicksort and mergesort are much more efficient!

An interesting point to note, the built-in sort used by Python employs many different types of sorts, depending on the size of the array passed in, which is why it is faster than all of the sorts mentioned above - it makes use of all the benefits offered by various sorting algorithms!