Sorting and Efficiency

Algorithm runtimes are important for large-scale inputs--the larger the input, the bigger the difference between an iteration of a logarithmic algorithm and an exponential algorithm.

Sorting, in programming, is taking a collection of objects and putting them in the order  needed by the function (ascending, descending, etc.).  In particular with Large N inputs, the initial order in which the objects are given will determine how fast (or slow) the algorithm runs.  For most types of algorithms, if the collection is already sorted, it will run faster (less assignment steps); if it is random, it will run slightly longer with the probability that some  things will be in order; if it is reversed, it will run the slowest because it has to re-assign every element of the list.

Here's a synopsis of some of the run times in Big-Oh Notation:

O(1) = constant
examples: a method that's algorithm is independent from the length of the input
why:  the method will always execute a certain number of steps that doesn't involve running the entire list, and thereby doesn't depend on the size of the input to determine its runtime

O(log n) = logarithmic
examples: a binary search three
why: the length of the input will be repeatedly cut in half when the algorithm runs, thus cutting the runtime of each subsequent section down by 50%

O(n) = linear
examples: searching through a list
why: running from one end of the list to the other (in a worst case scenario) searching for something will mean that the loop in the algorithm will iterate n times--where n is the length of the input

O(n^2) = quadratic
examples: comparing elements in a list
why: two loops will have to be written in the algorithm; one will run like the linear version (checking every element of the list), while the inner loop will compare the element from the first loop and compare it to every other element in the list--thus, for every n times the out loops is performed in a worst case, it is run n times with the inner loop.

These deal with the idea of efficiency because you want to create the fastest run time possible as a programmer, while executing exactly what your program is designed to do.  With the different types of Sorting Methods (Bubble, Selection, Insertion, etc.) it is easy to see, just by looking at the code, that there are less and more efficient ways to sort a collection of objects.

For example, Bubble, Selection and Insertion sort all have a "worst case" runtime of O(n^2) because in the worst case scenario, they will have to compare every element in the list with every other element in the list, reassigning everything.

Alternatively, something like Merge Sort has a faster "worst case" runtime of O(n log n), because it breaks the length of the input (n) into smaller subsections and re-orders those, sort of gluing the whole things back together, instead of checking one item across the length of the list.

As was tested in the lab, there are hybrid methods that combine certain techniques to create even faster run times, and with inputs of Large N, the reduction in Big-Oh upper bounds for the runtime will make a significant difference.