Week 11: Sorting and Efficiency

Here is this week's prompt for a slog entry: "You should explain what you've learned from readings and lectures about how to express the time complexity of some common sorting algorithms. Without regurgitating other sources, you should demonstrate some understanding of the characteristics of the different algorithms we've looked at."

Efficiency, which I briefly discussed in my last entry, is a crucial aspect of code. Generally, programmers consider an algorithm's worst case, best case and average case when thinking about the efficiency. This helps improve the algorithm and prepare for every extreme. If the time it takes to run an algorithm is constant and independent of "n" (size of input), its is noted as O(1). If the time it takes to run increases proportionally with respect to n, then it is noted as O(n). If the algorithm splits the problem up into parts, its usually O(lg n). This type of run time is usually very quick and efficient.  Algorithms with O(n^3) or O (n^2) are considered quite inefficient. There are many types of running types, some of which I semi- explained. There is constant, logarithmic, linear, quadratic, cubic, exponential and even worse. We generally consider the worst case when trying to assess what the big-Oh of an algorithm is. 

We learned about sorting functions in lecture as well. In CSC108, I had been introduced to some sorting methods including, bubble sort, selection sort and insertion sort. In lecture I was introduced to merge sort, count sort and the built-in sort method. All of these sorting techniques gets the same job done but with different efficiencies, which becomes more and more important with increasing size of what needs to be sorted. 

Selection sort finds the smallest element and swaps it with the first element until the list is fully sorted. 

Insertion sort iterates through a list and compares each item to the one before it until it can find the right place for that item and inserts it there. This continues until the list is sorted.

Merge sort is a recursive algorithm that breaks down a list into sub-lists and recursively sorts them using a base case of a list with one item. It than takes these sublists and puts them together to make one sorted list. 

Quick sort is another recursive algorithm. It chooses a pivot and puts items less than the pivot on the left and the items more than the pivot on the right. It recursively moves into the left and right with new pivots. On the left, the pivot will be smaller and greater on the right.  This continues until a list with only one item is found, which is the base case. At this point the list is sorted.