Week 11: Last but Most Efficiently...

Over the course of the last few weeks we were introduced the the concepts of code run-time and efficiency in various types of sorts. Although there are many different types of sorts, we mainly went into selection sort, insertion sort, quick sort as well as merge sort. Each of these different types of sorts had various concepts, algorithms as well as run time. In selection sort, the program iterated through the list and finds the smallest element and places it at the beginning. Insertion sort is a different type of sort where the program iterates through the elements in the list to be sorted and compares each element to the previous sorted elements until it finds the correct location for the element. Quick sort is a recursive sorting method where the program chooses a pivot and orders the elements less than the pivot to the left of the pivot and elements greater than the pivot to the right. This is then recursively on the sub lists created with a pivot smaller than the original pivot and a pivot greater than the original pivot until the base case of a size 1 list is reached, meaning that the sorting is completed and the list is sorted  Merge sort is an entirely different concept where the program breaks the list into many smaller sub lists and once again using recursion takes the base case of a list size of one which is assumed to be sorted and merges the sub lists back together and sorts the sub lists until one giant sub list is created with the same amount of elements as the original sub list. The topic of run times comes up quite frequently when analyzing and comparing these different sorts, and therefore we were introduced to the measure of algorithm performance O(n)[Big-Oh]. This measure to be efficient has to only measure the algorithm and be independent of hardware, programming language as well as random events. In O(n) measure we compare the algorithms running time in comparison when running a very large input of size n and compare how the running time of the algorithm changes as we change n. There are many types of running types such as constant run times(consistent for all size lists), logarithmic(very quick as it divides the list into small parts effectively, efficiently and quickly), linear(runs as fast as their are elements), quadratic, cubic, exponential and horrible algorithms. Because O(n) is an upper bound of sorting, we mainly worry about the worst case situations and compare the various sorts based on their worse case as the chances of obtaining and list with the perfect criteria or selecting the "perfect" pivot is very slim and almost impossible. Through the knowledge of sorts and the ability to analyze their algorithm running time, we are able to effectively compare various kinds of sorting algorithms based on their worst case situations and see what kind of impact the size of the given list, n, when very large, impacts the overall running algorithm running time.