Week 11: Sorting and Efficiency

    Last two weeks, we learned about sorting and efficiency. In terms of efficiency, the major concentration is on running time complexity. To compare different algorithms, we should make a choice on standards. For sorting algorithms, we choose the length of a list as one standard. And also, we ought to find a measurement counting for one 'step'. For example, in 'insertion sort' algorithm, we may choose one assignment statement as one 'step' or one comparison as one 'step'. Running time complexity of an algorithm may get various results  based on different standards. For instance, we may have running time complexity of '5n^2+3' based on one standard and 'n^2+log n' based on another. That is the reason why big-oh notation so useful. It provides an asymptotic upper bound for an algorithm. In the previous example, both '5n^2+2' and 'n^2+log n' belong to O(n^2). That significantly reduce the troubles when comparing two algorithms' running time complexity. Follows I will write down some sorting algorithms I have learned.
    In CSC108, I learned three O(n^2) algorithms: bubble sort, insertion sort and selection sort. These two weeks I learn some more efficient sorting algorithms: quicksort(O(n log n)), merge sort(O(n log n)), count sort(O(n) but it has preconditions), Tim sort(O(n log n), used in Python built-in sorting method). To get detail information about these algorithms, refer to these links: http://interactivepython.org/courselib/static/pythonds/SortSearch/sorting.html
http://en.wikipedia.org/wiki/Timsort
http://en.wikipedia.org/wiki/Counting_sort
    The common characteristic of bubble sort, insertion sort and selection sort is that they check items one by one. So intuitively, it is correct to have same asymptotic upper bound. Specifically, bubble sort repeatedly compares neighbour pairs and swaps if necessary, insertion sort repeatedly adds new element to the sorted result and selection sort repeatedly picks the smallest element to append to the result. Quick sort, merge sort, Tim sort are all 'divide and conquer' algorithms. Basically, they split the whole list into two halves and run recursively until reach the base case. So similar with binary search, dividing a list to two halves requires running time 'log n'. Roughly, on length n, we have running time 'n log n'.
    I caught a good website of learning sorting algorithms from my classmate's SLOG(http://lbg940131.blogspot.ca/): http://bigocheatsheet.com/. I strongly recommend it. I also recommend this SLOG(http://lbg940131.blogspot.ca/). Its analysis is sound and in depth.