Week 11 – Sorting and Efficiency

              Sorting is a powerful tool to find an item very quickly at a low computation cost. There are plenty of algorithms to choose from, each one has their advantages and disadvantages. Sorting can be used for many data types. An example of a sorting algorithm is the quick sort where you choose a pivot point; decide where the pivot point goes with respect to the rest of the list, and quick sort the remaining partitions until you have none left. This sorts our list very quickly and we can now find and pull out data out of the list fairly quickly, better than when it was unsorted. Another sorting algorithm is known as the merge sort where you divide the list in half and merge sort the halves (think recursion), after you merge the sorted results back into one list. Once again, a very simple and quick sort to have lying around. Efficiency is also known as Big-Oh, an upper bound for the runtime of an algorithm. The algorithm will never run longer than the upper bound that it was after a point C. The quick sort algorithm is Big-Oh of n lg n which can be rewritten as O(n lg n). This means that quick sort will never take longer than n lg n and will always be below it, thus it has a great efficiency of getting its job done.

              Something new I learned in class this week was how to make a sorting algorithm using recursion. Big-Oh was already known to be from a class from the last semester (CSC165). Nothing this week frustrated me and it was all clearly understood by me. Overall I feel very confident with the material this week. This week’s tutorial was the last tutorial which was saddening because the TA was one of the best I’ve ever had yet.