Week 11: Sorting and Efficiency

The past two weeks in class, we have looked at different types of sorting algorithms along with their runtime, which was also seen in big-Oh notation. In the lab this week, we also ran different types of sorts and noted their run time in comparison with others, but also ran these different sorts with three different types of lists of various sizes: random, sorted, and sorted and reversed. Through this lab, I saw that the python built-in sort was the quickest because, as our T.A. explained, all built-in python functions are written to be the most efficient; therefore, if there is a python built-in function, we should use it instead of writing our own code for it.

In CSC108, we were introduced to some of the different types of sorting algortihms, which included insertion sort and bubble sort. The algorithms we ran in the lab included these ones, as well as merge sort, quick sort, and selection sort.

Quick sort:
Quick sort works by choosing a pivot and then splitting the rest of the list into two, those greater than the pivot and those smaller than the pivot. Then, quick sort is performed again on the two separate lists. We looked at run times for choosing a pivot at the beginning of the list or choosing a pivot at random. When chosen at random, the run time was smaller than when the pivot was the first item because if the list was already sorted, in either ascending or descending order, the code would have to make every item a pivot before the code is complete.

Merge sort:
Merge sort works by splitting the list in half continually, then sorting and merging each of these halves until the list becomes one sorted list. The run time of a sorted, random, or sorted/reversed list is the same every time for merge sort because it will always perform the same steps, no matter what order the numbers are in. The big-Oh notation for merge sort is O(nlogn).