The run-times of algorithms in computer science are categorized using different function types (logarithmic, exponential, polynomials, etc.) and the relationships known as big-Oh, big-Omega, and big-Theta. In this particular course only big-Oh was considered with any depth. Given an input of size n and an average run-time of g(n) for some algorithm, g(n) is said to be in big-Oh of another function f(n) - denoted O(f(n)) - if for a certain input size and beyond, f(n) multiplied by some constant is an upper bound for g(n). Mathematically speaking there exists a real constant and a natural constant such that for all inputs, if n is greater than or equal to the natural constant then g(n) is less than or equal to f(n) multiplied by the real constant. Big-Omega mirrors this relationship with a lower bound and big-Theta is the case when both the lower and upper bound requirements are met for one f(n).
These notations are useful for approximating nasty representations of run-times and comparing algorithms. In regards to comparison, the notation used with a particular function can be viewed as a set of functions who satisfy the "big" definition with respect to that particular function. Those sets that revolve around faster run-times are subsets of those centered at slower run-times.
For example: O(1) is a subset of O(log(n)) which is a subset of O(n) and so on.
Efficiency is often taught in conjunction with all kinds of sorting algorithms. These sorting algorithms all have well understood big-Oh classes. The weakest of them are the bubble, selection, and insertion sorting algorithms whose run-times are all O(n^2). I'm going to give a whirlwind tour as to how these algorithms work. Also each of these algorithms are traditionally demonstrated on a list L containing integers. To be sorted means that the integers are arranged "smallest-to-largest" from index 0 to len(L) - 1.
Bubble Sort:
At a given step a starting value is assigned and is compared with the next element. If the value is greater than the element their positions are swapped, otherwise the next element becomes the value for comparison as you iterate over the list. When a given element assigned to the comparison variable reaches the end of the current iteration a new one begins with the alteration that the iteration spans one index less than the previous iteration. This is because beyond and including that separated index is already sorted. Ultimately elements bubble up to their final positions.
Selection Sort and Insertion Sort:
Like bubbling, these algorithms utilize a barrier to distinguish between what has and has not been sorted. The main difference being that the barrier moves from the front of the list and therefore increases the starting point of a new iterative step. Selection sort works analogously to bubbling where it instead finds the smallest element and places it in the greatest position of the sorted part and then moves that barrier. The insertion technique sorts on the fly by comparing a given value to the sorted part and places it accordingly, all the while moving the barrier as it goes.
The next class of sorting algorithms are generally much more efficient but the preceding three (ok perhaps not bubble sort) do have merit when applied to small lists. The faster sorts I'm referring to are called quick sort and merge sort. The latter is O(nlog(n)) with the logarithm of base 2 and the former at its best also meets this run-time classification.
Quick Sort:
The idea here is to choose a pivot element at which a left and right list are created. The left list is a sorted list of all the elements less than the pivot and the right is a sorted list of all the elements greater than the pivot. Bringing them together would then generate the desired list. Now how are the left and right lists sorted you may ask? Recursively. Eventually the calls will cause the lists to be single values and then the recursion can make its way back up to the top. I made notion to the fact that quick sort's run-time class can change depending the choice of the pivot with respect to the conditions. By conditions I mean the length of the list and to what degree it is unsorted. A good choice in pivot results in a run-time of O(nlog(n)) but a poor choice can result in quadratic run-time.
Merge Sort:
Somewhat similar to quick sort except the list is divided in half (sometimes approximated via integer division) and the sorted halves are merged by moving through and comparing the items in parallel from the largest to the smallest and appending these values to a third new list . The new list becomes an extension of the smaller lists to generate the merge. Recursive calls are made on the halves.
These are the main sorting techniques studied in CSC148. The other obvious one to mention is python's built-in sort which is far faster than any of these. Firstly it's highly optimized such that depending on the conditions of the list provided it will employ the most efficient algorithm. It can make those distinctions part way through its sorting. For example, if a merge sort generates an acceptably small halve insertion sort will be used instead of the recursive call. Secondly in the python environment it has the advantage of being written in C. This is a lower level language that is more akin to what the processor directly understands.
No comments:
Post a Comment