Sunday, March 30, 2014

Sorting and Efficiency

Today I would like to introduce several sorting method by python language and compare their efficiency by Big O

First one: Insertion Sort

def insertion_sort(sort_list):
     iter_len = len(sort_list)
     if iter_len < 2:
         return sort_list 
    for i in range(1, iter_len):
         key = sort_list[i]
         j = i - 1 
        while j>=0 and sort_list[j]>key:
             sort_list[j+1] = sort_list[j]
             j -= 1 
        sort_list[j+1] = key
    return sort_list 

Insertion sort has two nested loops:
Outer loop runs once for each element in the original unsorted loop
Inner loop runs through sorted list to find the right insertion point
And thus the efficiency is O(n^2)

Second one: Selection Sort

def selection_sort(sort_list):
     iter_len = len(sort_list)
     if iter_len < 2: 
        return sort_list
     for i in range(iter_len-1):
         smallest = sort_list[i]
         location = i 
        for j in range(i, iter_len):
             if sort_list[j] < smallest:
                 smallest = sort_list[j]
                 location = j
         if i != location: 
            sort_list[i], sort_list[location] = sort_list[location], sort_list[i] 
    return sort_list

The basic idea of selection sort is: 
For each element i in the list:
1) „Find the smallest element j in the rest of the list
2) Swap i and j
And thus the efficiency is O(n^2/2)=O(n^2)

Third one: Bubble Sort

def bubble_sort(sort_list):
     iter_len = len(sort_list)
     if iter_len < 2:
         return sort_list
     for i in range(iter_len-1):
         for j in range(iter_len-i-1):
             if sort_list[j] > sort_list[j+1]: 
                sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j] 
    return sort_list

The basic idea of bubble sort is:
Run through the array, exchanging values that are out of order
Outer loop can execute a maximum of n-1 times
Inner loop can execute a maximum of n-1 times
And thus the efficiency is O((n-1)^2) = O(n^2)

For now we can see that the three sorting algorithms introduced above all have the same efficiency O(n^2)
So do we have any more efficient algorithm?
And the answer is Yes!

Fourth one: Merge Sort

def merge_sort(sort_list):

    def merge2(L1:list, L2:list) -> list:
        L = []
        L1.reverse()
        L2.reverse()
        while L1 and L2:
            if L1[-1] < L2[-1]:
                L.append(L1.pop())
            else:
                L.append(L2.pop())
        L1.reverse()
        L2.reverse()
        return L + L1 + L2

    if len(sort_list) < 2 :
        return sort_list
    else :
        left_sublist = sort_list[:len(sort_list)//2]
        right_sublist = sort_list[len(sort_list)//2:]
        return merge(merge_sort(left_sublist), merge_sort(right_sublist))

The basic idea of Merge Sort is:
1)Break the data into two equal halves
2)Sort the halves
3)Merge the two sorted lists
And here we sort the halves by recursion
It's easy to find out that the efficiency of step Merge is O(n)
And it's also not difficult to conclude that the number we splits the list is O(logn)
And thus the efficiency of Merge Sort is O(nlogn) < O(n^2)






















3 comments:

  1. I think your analysis of each algorithm is in depth. You explained soundly the reason why certain algorithm has this asymptotic upper bound.

    ReplyDelete
  2. i think your explanation of each algorithm is very concise and clear! very useful!

    ReplyDelete
  3. The idea of MergeSort really helps!

    ReplyDelete