Even in 108, we were advised to think about efficiency in our functions, and we learned about some sorting algorithms. We looked at for-loops, and for-loops within for-loops that caused the program to make linear and quadratic amounts of steps, respectively. In 148, we were given a more expansive hierarchy of function efficiency, determined by running time analysis for an input of size n. Here it is:
constant: c (a number in the range of positive rational numbers)
logarithmic: clogn eg, binary search
linear: cn eg, linear search
quadratic, cubic, etc: cn^2, cn^3, ...
exponential: c2^n eg, tower of hanoi
horrible: cn^n or cn!
In the same lecture, we were refreshed on big-oh notation from 165. To understand big-oh, you need to first understand worst case scenarios and break-points. big-oh always considers the worst case scenario (the longest possible time it will take to complete the function) of a function of a given running time analysis. For example, O(n) means the worst case scenario for a function of running time analysis n
When comparing big-ohs to other big-ohs, you need to consider a break-point. A break point is a certain size of input where one function is no longer taking more time at it's worst case scenario than the other function. Also, if one function always has a longer running time analysis than the other, then the certain break-point is considered to be 0. For example,
O(n) is a subset of O(n^2)
Means that at a certain break-point, the worst case scenario for a function of running time analysis of n^2 is worse than that of one of running time analysis of n for all sizes n that are larger or equal to the break-point. I know it's a wordy definition, but after a couple of visualizations, it's not a difficult concept to understand.
Running time analysis is always the focal point when creating an efficient sorting algorithm. In 108, we already learned about some less-than-stellar sorting algorithms, mainly bubble sort, selection sort, and insertion sort. Now, we're learning about quick sort, merge sort, count sort, and tim-sort (tim-sort is python's built-in sort function).
Quick sort is the first of these sorting algorithms we learned. It works like this:
1) Choose a pivot (preferably at random)
2) Check every element besides the pivot. If the element is less than the pivot, it goes into list L1
If the element is more than or equal to the pivot, it goes into list L2.
3) return L1 sorted by quick_sort, concatenated with the pivot, concatenated with L2 sorted by quick_sort.
A pivot is chosen randomly to help ensure the largest or smallest element doesn't get chosen. That way, there is less chance of going recursively into only one list that simply excludes our pivot. That would make the function much less efficient.
When running through these steps, it's important to remember that a list of 1 or 0 is considered sorted. That is the base case for this sorting algorithm, and for the following one.
Merge sort is the second of these sorting algorithms we learned. It works like this:
1) Cut the list roughly in half.
2) merge_sort each half.
3) merge those halves together.
Two functions are happening here: merge_sort and merge. merge is important because it's often needed to make sure that the list that combines the two sorted lists [0, 2] and [1] is also sorted, as list [0, 1, 2] instead of [0, 2, 1]. merge_sort basically breaks down the list into many halves-of-halves-etc. until it's entirely lists of length 0 or 1, and then they are all merged together properly with merge.
Thanks to the clever use of recursion, these two sorting algorithms have a logarithmic running time analysis, meanwhile sorting algorithms learned in 108 had a quadratic running time analysis. That's an incredible difference in sorting efficiency!
No comments:
Post a Comment