Week 11 - Sorting Algorithms

          There are many different sorting algorithms that sort information into various types of orders with varying efficiencies. (From the least inefficient - bubble sort - to one of the most efficient - quick sort)  The many different algorithms each have their pros and cons, excelling at list of smaller sizes but are weaker when dealing with lists of a large size - meaning that their runtime grows to a staggering amount in proportion to the size of the list. And then there are some sorting algorithms that excel over others when the input is a large list. The order in which the information is arranged prior to being sorted using a certain algorithm also affects runtime - this depends on the process in which a function sorts a list. It is important to know the worst case runtime of an algorithm. To do this, you need to calculate the time complexity of an algorithm and represent it using big O notation which describes the behaviour of a function. 

Here, f(x) - blue and g(x)- red. f(x) ∈ O(g(x)). Big O notation can be used to describe the worst case runtime of a function’s algorithm. For example, bubble sort has a worst case runtime that is quadratic, O(n**2) which means that, depending on the imput size, the runtime will increase quadratically in proportion to the size of the list. If you analyze the code for bubble sort:

def bubbleSort(alist):

    for passnum in range(len(alist)-1,0,-1):

        for i in range(passnum):

            if alist[i]>alist[i+1]:

                temp = alist[i]

                alist[i] = alist[i+1]

                alist[i+1] = temp

         You will see that on line 2, you are dealing with a list of size n and on line 3, you are also dealing with a list of size n, therefore n * n = n**2, so the runtime at worst is n**2 - we care most about the highest exponents. For example, the the runtime is n**2 + 3n + 6, this means that the runtime is O(n**2). Selection sort improves on bubble sort considering the number of passes, it swaps the largest in the list with the smallest consistently, however, the runtime is still O(n**2) and so is the runtime of insertion sort at the worst case which inserts a value in its correct place from beginning to end. Shell sort is also O(n**2) at worst - it splits a list into sublists and sorts the sublists before piecing the list together again. Merge sort is a recursive algorithm which constantly splits a list in half and sorts smaller lists before rearranging the split list together with a worst case runtime of O(nlogn). Quicksort improves upon merge sort because it does not use additional storage, it uses a pivot point, a value that is used to split the list and then calls itself recursively to sort smaller lists. Quicksort is on average O(nlogn) and faster than most O(nlogn) algorithms although, the worst case runtime, O(n**2), is rare. There is also Timsort (O(nlogn)), a hybrid sorting algorithm that merges insertion sort and merge sort. You can also measure the best case runtime (represented by big omega) and the average case runtime (represented by big theta). However, if someone needs a sorting algorithm to sort a lot of information at once or in various different orders, then an algorithm is only as good as its worst case.