Week 11

During week 11, we've discussed the performance and efficiency of the sorting algorithms. As a continuation from last week, our professor touched on some topics regarding Big Oh. Personally, I was confused how I can determine the Big Oh of an algorithm simply based a given code. In order to have a clear understanding how one code can differ in runtime, I have used online resources. I found that the first thing I must check is what kind of job a function(searching, sorting, etc...). It is easy enough to see that the sorting takes longer time than searching. The worst runtime for sorting(including those discussed in class and lab) was O(n^2) while the worst for searching(including binary search and linear search) was O(n). During lab 10, the main task was to graph the runtime of the sorting algorithms. Based on the graph, my partner and I guessed and checked the efficiency of each cases. At the end we figured out the sorting optimization for selection sort, insertion sort, bubble sort, merge sort, quick_sort, and list sort. The key in determining each algorithm's efficiency was whether or not the list was nearly sorted and whether or not the list was reversed. Given an item, multiple of 400 elements in this lab, the selection sort had no particular best or worst cases; its performance was always O(n^2). For insertion sort, the best case was when the list was already sorted; worst case was when the list was reversed. For bubble sort, best case happens when the list is nearly sorted since the bubble sort will terminate after first iteration; the worst case happens when the smallest element is located at the large end of the list. For merge sort, both increasing and decreasing ordered list will give best case; if the input alternates between large and small value, it would give the worst case (more comparison needed during the process). For quick sort, the sorted list generates the worst case because then the pivot is always the largest element, meaning the list is sub-patitioned into sub-arrays of n-1 and 0. Overall, according to the general observation we had in lab, Python's built-in sorting function was the most efficient algorithm out of all.