Week 11 - Sorting and Efficiency

When coding, it is important to make code efficient; after all, who would willingly choose to use a slower code? While two algorithms may only differ by .001s over say, a list of 10 numbers, that difference between algorithms may grow exponentially over a list of hundreds of thousands of numbers.
Im not going to go over how the different algorithms sort, as that was my post for last week. This post is mainly going to discuss the efficiency of the sorting algorithms. So, all the algorithms I mentioned - Insertion, Quick, and Merge sort - all are capable of sorting a list of numbers. However, Quick and Merge sort are much more efficient choices. To show this, we can look at their worst run times, denoted by O(?). This is called big-O notation.

Insertion Sort
Insertion sort is O(n^2). This means that in the worst case, the runtime is proportional to the square of the size of the list. In insertion sort, the worst case would be a reverse sorted list, as each item would have to be moved to the back (left) of the sorted section.

Quick and Merge Sort
Quick and Merge Sort are denoted as O(nlogn). The logn represents the runtime of splitting a list in two pieces. The we choose log of n, as it is relative to how many splits of the list we perform. The n in the O(nlogn) is the efficiency of the action performed after the list is done splitting. For example, it is the runtime of the merge action in merge sort. Combining these two; the splitting and the merge, we get a total runtime of O(nlogn).



This graph shows us various big-O runtimes. As we can see, over large sets of data, O(logn) takes less time than O(n^2). We can then conclude that Merge and Quick sort are more efficient than insertion sort, and thus in applications of sorting, we should use merge and quick sort.
Theoretically, the best possible sorting algorithm is O(1). that is to say that no matter the size of the data input, the runtime of the function is constant. Of course, an algorithm with this runtime has yet to be discovered over all sets of data.

It is important to note that big O notation only concern the worst-case. Under ideal conditions, or even average conditions, it could be possible for two algorithms to perform equally, only differing under big-O restrictions. You should therefore also consider average and best runtimes, in addition to the worst case, when deciding which algorithm to use.

Thats it for this entry, and my SLOG as well! Initially I had doubts about the usefulness of SLOGS, as did many of my friends, but as I have written them, I do have to admit that they have helped me better understand some of the concepts we have learned. I enjoyed the course, and wish everyone the best!