Blog Entry #5 : Sorting and Performance

Blog Entry #5: Sorting and Performance 

Nov 4th - Nov 9th


        In last week's lecture, we "reviewed"  a few sorting algorithms: selection sort, merge sort, and quick sort. In this week's blog, I will briefly talk about each sorting methods and its performance.

Selection Sort
       The algorithm behind selection sort is fairly simple: keep finding the smallest item and swap it with the replacing item.

    L1 = L[:]
    for i in range(len(L1)):
        m = min(L1[i:])
        j = L1.index(m,i)
        L1[i], L1[j] = L1[j], L1[i]
    return L1

     
       In the average case scenario, the code will run n times to find the first smallest item, and then (n-1) times to find the second smallest item, and then (n-2), (n-3)...2,1. In total, the program runs n (n-1) / 2 times, therefore the performance in big-oh notation is O(n^2). In my opinion, even selection sort on average is not as efficient as quick sort or merge sort (which I will explain in more details later), the coding itself and the algorithm are much simpler. Also the performance t is always O(n^2) no matter the given list is sorted or not.

Merge Sort
       Merge sort is based on the divide-and-conquer paradigm.
     
       Step #1; Recursively dividing the given list into n sublist, each containing 1 item

           if len(L) < 2 :

          return L[:]
      else :
          return merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))

       Step#2: Sorting all sublists

        while L1 and L2:

          if L1[-1] < L2[-1]:
              L.append(L1.pop(-1))
          else:
              L.append(L2.pop(-1))

       

        Step#3: Combining all sublists

        The average and best cases performance for merge sort are both O(n log n). To sort a given list N with n elements, 2 lists N1, and N2 (half size of the list N) is recursively sorted plus n steps to merge them back to one single list. However, while I was searching various sorting methods and its performance online, I found it interesting that natural merge sort (a sequence of ascending than descending numbers) only takes O(n) running time on a sorted list. 

Quick Sort

       Quick sort is also known as partition-exchange sort, and the idea behind it is to recursively choose any item as the pivot and sort the list by items smaller than the pivot, pivot, and the items greater than the pivot. 

      

      Similar to merge sort, the average performance of quick sort is also O(n log n), it takes O(n) to call the pivots and recursively calls two half-sized sublist.

      In theory, the pivot can be any item in the list. However, the best decision of pivot can divide the list into two equal (or almost equal) halves, and the worst case of scenario is that one of the two sublist is empty. Clearly the choice of pivot have a great impact on the performance. 

       

quick([x for x in L[1:] if x < L[0]])

                + [L[0]] + quick([x for x in L[1:] if x >= L[0]])

     The exercise we did in class simply assume the far left element as the pivot. Unfortunately, in this case, if the given list is sorted, it will create the worst case performance O(n^2).