Sorting and Efficiency:

       One of the most important aspects of programming is efficiency. Efficiency of a program is how fast it can compute, given a large set of data, as compared to another program with a different algorithm. We briefly covered this topic in CSC108, where we learned about efficiency using the sorting mechanisms: bubble sort, selection sort, and insertion sort. The efficiency of these sorting mechanisms (bubble sort, selection sort, and insertion sort) was compared using their big oh definitions, where all three of them were denoted by O(n²). The big oh for these algorithms denotes what happens as the data inputted gets larger but they can be compared as still have advantages and disadvantages when given smaller input size. For example, bubble sort compares two numbers and swaps them if the second number is smaller and continues to take the larger of the two compared throughout the list while comparing with the consecutive number until it places largest number to the back of the list. When it starts back again it makes one less comparison each time. Whereas, in insertion sort it picks the smallest item and places it to the front of the list repeatedly, building a sorted sublist. When comparing bubble sort and insertion sort, insertion sort is slightly better because of the fewer swaps it makes even though the big oh denotes for these two functions is the same.

       
       Recently, we were introduced to three more sorting algorithms, which are merge sort, quick sort and count sort. Since CSC148 hammered recursion into our brains, these sorting techniques also dealt with recursive techniques to provide greater efficiency.

       One of the new techniques we learned is merge sort, where a list is divided into two halves and each piece is “merge-sorted” and this process continues till each list contains only one element. When a list has one or zero elements it is already sorted. These pieces are then merged back together. Since I can’t display the technique using cards as done in class, the following diagram from one of the readings is gives great visualization for understanding the merge sort technique:

© Copyright 2013 Brad Miller, David Ranum

Retrieved from: http://interactivepython.org/courselib/static/pythonds/SortSearch/sorting.html

      The use of recursion in merge sort allows its efficiency to be O(nlogn). Although I wish I had understood why its efficiency is so before writing TT2, there’s no harm explaining it now since I actually understand it. The logn part of big oh comes from the division of the list in halves, which makes sense because as the rate of increase in x values in a logarithmic function increases, the rate of increase in y values decrease. Thus, the number of divisions of the list also decreases as the list is parsed in smaller sublists. The n part of the big oh comes from the merging of each number. In other words, the function merge is called n times because the division of the sublists leads to n lists (as each sublists contains 1 element). Merge sort, in comparison to the sorting techniques learned in CSC108, is much more efficient because O(nlogn) > O(n²).

      The second sorting technique we learned is called Quick sort. Quick sort works by picking a split point, called pivot. Then it makes sublists of items that are smaller than the pivot and larger than the pivot, and recursively solves these sublists till each sublist has less than 2 elements. Just like merge sort, a list is sorted when it contains only one element in it, which is essentially the base case. Below is a diagram that provides a clear example of quick sort:

Retrieved from: http://kehs.ksd.org/Classes/Compsci/Java/WebLessons/ICT%20Version%201.5/WebLessons/APCSL26/APCSL26-1-3.html

Unfortunately, the worst case scenario in quick sort is denoted by O(n²) which is accounted by the choice of pivot which can be the two ends of the list each time, causing n divisions and the processing of each item’s placement in the final sorted list. However, when the pivot is always the middle element the runtime analysis can be O(nlogn), similar to merge sort.

      Lastly, we also looked at count sort in class, which Danny had made up in just a few minutes before class (Wow!). The following is the code for count sort, presented by Danny, since there aren’t any visuals online:

def count_sort(L):
    """silly functional sort.  See radix sort for something serious"""
    count_list = [0, ] * len(L)
    for i in L:
        count_list[i] += 1
     L1 = [] # blank slate!
    for i in range(len(count_list)):
        for j in range(count_list[i]):
            L1.append(i)
    return L1

     
      Although count sort doesn't use recursion, the way that it works is by making an initial list of zeroes, where there are as many zeroes as the number of elements in the list plus 1 extra zero. Then, the original list is iterated over to mutate the index correlating with each item’s value with 1 in the place of zero in the list of zeroes. Lastly, a new list is created to append the values of the index containing 1. Here is an example of a list that goes through count_sort:        count_sort([3,1,2]) à count_list = [0, 0, 0,0]

                                                                      à count_list = [0, 1, 1, 1]

                                                                      à L1 = [1, 2, 3]

#this final list contains the indices of value 1 in count_list

       As evident, this sorting technique would fail if a value of the list was greater than the value of the total length because its corresponding index in count_list will not be incremented by 1, thus leaving its value out. Nevertheless, this sorting mechanism is denoted by O(n) because the actual list is iterated over only once.

       So, these sorting algorithms provide us with a tool for comparing the runtime analysis!