A sorting algorithm is an algorithm for sorting a set of elements. Different algorithm may be better for sorting under different circumstances. For example, even the worst and average case running time of merge sort and bubble sort are the same(both are O(n^2)), their best case running time are different: the best case running time of merge sort is nlog(n), and bubble sort is n. This explain why the bubble sort is better than merge sort in practice for small set of data, but as size of input data increases, the performance of bubble sort suddenly drop down and the exact opposite behavior can be found with merge sort.
The graph below shown nlog(n) vs. n
n is the linear line, and nlog(n) is another.
Another example is to show how one sorting algorithm is better than another. We now compare quick sort and bubble sort.
Even though the worst case running time of bubble sort and quick sort are both n^2, their average case running time are different:
the average running time of quick sort is nlog(n), and the average running time of bubble sort is n^2.
The graph below will illustrate the behavior of their running time:
Therefore, obviously that the quick sort is better than bubble sort.
Also, in our lab #10, we worked through different kinds of sorting algorithms and record the results on chart, and then plot the result on a graph. The aim of this lab is to investigate how various sorting algorithm works.
Here are some worst case running time of sorting some often used sorting algorithm, i think to be familiar with them will be help on our test:
quicksort: O(n^2)
Merge sort: O(n logn)
Insertion sort: O(n^2)
Selection sort: O(n^2)
Bubble sort: O(n^2)
Since big-oh is an upper-bound, we have the hierarchy:
O(1) is a subset of O(lgn) is a subset of O(n) is a subset of O(n^2) is a subset of O(n^3) is a subset O(2^n) is a subset O(n^n).
