Week 11 - Sorting

Sorting is organizing a set in a certain order such from smallest to greatest or greatest to smallest. There many are different ways of sorting set such as Timsort, Merge Sort, Selection Sort and Insertion sort. Timsort works the same way as the sort built-in method found in Python itself. Merge Sort works by splitting the list into individual pieces and merging each of these pieces back together into a list that is sorted. Insertion Sort works by starting from the first item in the list and checking whether the next item is smaller or not. If it is smaller, it will be inserted after an item in the sort listed which is on the left side of the selected item that is smaller than it. Selection Sort works by splitting the original list into 2 sections, a sorted section on the left and unsorted section on the right. It moves the smallest item one at a time from the unsorted section into the sorted section. Basically, the sorted section starts off empty and eventually becomes the entire length of the original list and the original list would have been sorted.

However, what differentiates these sorting algorithms aside from how they sort is how long it takes to sort a set i.e its performance. Each way of sorting either via Timsort or Selection Sort or any other kind of sort require a number of steps before a set is sorted. For a n sized list, the performance of a sorting algorithm is categorized as either constant where the number of steps required to sort a list is constant non changing, or n where the number of steps depends on the length of the list i.e linear function or n^2 where the number of steps depends on the square of its length or n^3 where the number of steps depends on the cube of its length or nlogn and logn where it takes the log of the length of length for it to complete the sorting or finally 2^n or n^n where the number of steps required is either 2 to the power of the length of the list or the length of list raised to the power of the length of the list. These categories are in Big-Oh which is a way of representing the worse case or the upper-bound for the number of steps it is required for a sorting algorithm to sort a list. The best type of algorithms you have to is categorized by O(c) which means that the worst case for the algorithm is constant. That means that no matter no long your list, it will only do c number of steps. It is constant in that the number of steps do not vary depending on the length of the list. These type of algorithms are the fastest and most efficient. The worst type of algorithms you want to have is categorized by O(n^n) or O(2^n). These are exponential functions and take a huge amount of steps. A list of 5 items if the algorithm is categorized by O(2^n) would already require 32 steps to solve it vs just only 5 steps for an algorithm categorized by O(n). These exponential functions are really really slow and not efficient. Therefore, you want to avoid algorithms with O(2^n) or O(n^n).

As much as you want to avoid algorithms with Big-Oh of exponential functions, you also want to avoid using sorting functions or any type of methods or functions that are not built-in. The reason is that you are not a programmer and therefore the function you write is not optimized for the platform nor is going to work as well as the built-in methods. For example. the built-in sort function worst case is represented by O(n).where as the other kinds of sort that even the prof wrote such as Selection Sort or Insertion Sort still is only represented by O(n^2). This means that the built-in methods is always going to be better than what you can come up with. Therefore, you want to avoid having to write your functions and methods. It is always better to use built-in ones.