So during this week, sorting and efficiency was discussed
and the ways to categorize them. There are many kinds of sorts such as the shellsort,
insertion sort, selection sort, bubble sort, quick sort and many others; each
producing a sorted list whilst using different and or hybrid methods to sort.
And it is this difference in methods that allow for different sorts to have
different run time or efficiency.
Take bubble
sort for example, I can say that the big-Oh for this type of sort is n2
and this makes sense. Consider a list with 1 million items, the worst case
scenario in this case would involve running 999,999 iterations which is approximately
x2. Bubble sort runs by taking the item in question and comparing it
to the value next to it. If it is bigger it shifts the item to the right
otherwise, it stays the same and the next value is the new item in question. It
runs constantly through all the items in the list in which the list gets
shorter by n-1 times. So what is big-Oh? Big-Oh simply indicates the scaling of
the algorithm as the size of the list if items increases indefinitely in the
worst case scenario. Therefore, big-Oh value of n2 means it will
take n2 times long as the list grows big. In blunt efficiency terms,
it’s a terrible sorting algorithm to use for long lists.
Another
more efficient example is the merge sort. In this case, the value of big-Oh is
n log(n) and this can be explained by the nature of the sort. Merge sort uses a
divide and conquer approach where it breaks the list into 2 constantly,
relative to the first item in the list. I.e. the items that are bigger or equal
to the first item and the items that are less that the first item. This is run
many times until all the smaller broken up list are properly sorted and then
the merge begins. The breaking into two separate parts constantly is the reason
behind the log(n) and the n comes from figuring out the items that are bigger
or smaller than the first item in the list.
These
analysis of worst case run times can be used to identify good sorts but more
importantly choose the right sort for the problem in question. For example, although
bubble sort has a big-Oh value of n2 if the list is very close to
being sorted, the best case scenario for bubble sort becomes n. n being much
more efficient then n2 even though it is the same sorting algorithm.