Week 11: Sorting Algorithms

Once again this is a special week when i have an assigned topic to write about. The topic for this week is about sorting algorithms!  In CSC 108, we already studied 3 basic sorting algorithms, bubble sort, insertion sort and selection sort. Later, in CSC 148, we were introduced 3 more types, merge sort, quick sort and count sort. In this Slog, i will walk you through all 6 sorting techniques above and discuss the advantages and disadvantages of each technique.

1. Bubble sort: This is most fundamental sorting algorithm. It works basically by continuously comparing two consecutive elements in a list. If the first element is greater than the second one, then the two elements are swapped.  After finishing one pass, the biggest element will be left at the end of the list, it then again starts from the beginning of the list and repeating the process until no more swap occurs in the last pass. So, in the second pass, the second biggest element will be placed before biggest element at the end of the list. In the third pass, the third biggest is placed before the second biggest and so on.

The running time of bubble sort for both best and wort case is O(n²) for processing a list of length of n. However, if we make a variable that keep track of number of swap made per pass and terminates program if no swap was made after a pass. The best case running time of bubble is then reduced to O(n) and it happens when calling bubble sort on a list that already sorted. 

Advantages of using bubble sort:

• It is easy to code and easy to understand, so it's suitable for beginner who first learn how to program. 
• Bubble sort algorithm is usually very short and can be implemented using recursion.
• It is a stable algorithm, which means that it maintains the relative order of equal key.

Disadvantages of using bubble sort:

• Bubble sort very inefficient when dealing with large set of data since its running time is proportional to the square of the size of the list. 

The optimized bubble sort algorithm for Python:

def bubblesort(lst):
    for passes in range(len(lst)-1, 0, -1):
        swap = 0 # swap counter
        for index in range(passes):
            if lst[index] > lst[index + 1]:
                lst[index], lst[index + 1] = lst[index + 1], lst[index]
                swap += 1
        if swap == 0:
            break # escape the for loop if no swap after a pass
    return lst

2. Selection Sort: The algorithm works by dividing the list  into sorted and unsorted parts. There is a counter variable that store the index at the boundary between sorted and unsorted part in a list, the counter is initialized at 0. The algorithm iterates through the unsorted part to find the minimum value (ascending-order) or maximum value (descending-order) and swap it with the first element also in the unsorted part of the list. The counter is then incremented by one, making the first element (which also is the minimum/maximum) in the unsorted part to become the last element in the sorted part.

In order to fully understand selection sort, let consider an example. Given list L = [1, 2, 3, 100, 4], i will use selection sort algorithm to sort the list in descending order. Below is the algorithm and a table showing the position of all elements in list L after each pass:

def select_descending(L1): # selection sort algorithm
    for i in range(len(L1)-1):
        m = max(L1[i:])
        j = L1.index(m,i)
        L1[i], L1[j] = L1[j], L1[i]
    return L1

Original List L1		1	2	3	100	4
L1 after 1st pass	i = 0 From L[i:-1], 100 is the biggest number, 100 is swapped with element at L[i] which is 1.	100	2	3	1	4
L1 after 2nd pass	i = 1 From L[i:-1], 4 is the biggest number, 4 is swapped with element at L[i] which is 2.	100	4	3	1	2
L1 after 3rd pass.	i = 2 From L[i:-1], 3 is the biggest number, 3 is swapped with element at L[i] which is itself.	100	4	3	1	2
L1 after 4th pass	i = 3 From L[i:-1], 2 is the biggest number, 2 is swapped with element at L[i] which is 1.	100	4	3	2	1
L1 sorted		100	4	3	2	1

Selection sort shares some common advantages with bubble sort:

• It's really short and doesn't cost much memory for storing the code.
• It's easy to understand, suitable for beginner.
• Selection sort, in average, runs much faster than bubble sort since it does not require as many swaps as bubble sort.
• Run best when the size of the data is small. 

There are considerable disadvantage of using selection sort:

• It run really slow when the size of data is large.
• It does not maintain the relative order of equal key value, which means that it's unstable algorithm. 

Selection sort has constant running time T(n) = O(n²)

3. Insertion Sort: Again is another O(n²) running time algorithm, it is an efficient algorithm for sorting a small set of data. It works just like its name suggest, it sort a list by picking up a value in unsorted part and insert that value to a proper position in the sorted part of the list. Following is the insertion sort algorithm to sort a list in descending order.

def insertion_sort_descending(s):
    for i in range(1, len(s)): # moving the boundary
        val = s[i] # pick a 1st value in unsorted part
        j = i - 1 # get range of the sorted part
        while (j >= 0) and (s[j] < val): # loop through the sorted part from back to front
            s[j+1] = s[j]
            j = j - 1
        s[j+1] = val # put the value into a correct possition
    return s # return the sorted list 

Some advantages of using insertion sorts are:

• Although insertion sort slightly harder to be implemented than bubble and selection sorts, it is still fairly simple compared to O(nlogn) algorithms like merge sort or quick sort. 
• It runs swiftly in small size list as well as lists that are almost sorted.
• One of the biggest advantage of using insertion sort is that new values can be kept adding at the back of the data set (back of the unsorted part) when the data set is being sorted. In other words, it is real-time processing and may be suitable for some online applications. 
• It maintains the relative order of data with the same key. 

The only disadvantage for insertion sort:

• Although insertion sort is better than selection sort or bubble sort, it still not really efficient for large set of data.

The worst case time complexity for insertion sort is O(n²) and the best case is O(n), happening when the list is nearly sorted. 

4. Merge Sort: Let's define merge sort by looking directly at the algorithm for merge sort. There are two parts of this algorithm: 

Part 1: A helper function is used to combine/merge two sorted lists to make one bigger sorted list. 

def merge(L1, L2): # Prof Heap's lecture 10 code
    L = [] # lmerge list L is used to appended item from two list L1, L2
    i1, i2 = 0, 0 # define the two counters
    while i1 < len(L1) and i2 < len(L2):
        # Which ever element that is smaller will be added to the merge list L.
        if L1[i1] < L2[i2]:
            L.append(L1[i1])
            i1 += 1
        else:
            L.append(L2[i2])
            i2 += 1
    # if len (L1) != L2, any elements left in either list that have yet been
    # compared means that they already sorted so can be add directly to merge
    # list L.
    return L + L1[i1:] + L2[i2:] 

Part 2: The main function which is the actual sorting function doesn't do much beside from recursively dividing a given unsorted list into two sub lists. And when the length of  two sub lists is equal to one (a list of only one element is always sorted), it calls the helper function 'merge' to recursively merge the two sorted sub lists together. 

def merge_sort(L): # Prof Heap's lecture 10 code.
    # Base case: if len(L) == 1, means that L is already sort
    if len(L) < 2 :
        return L[:]
    # If len(L) > 1 means that L may not be inordered.
    else :
        # Recursively merging two sorted lists to make a bigger sorted list
        return merge(
            # Recursively divide the list into two smaller sublist.
            merge_sort(L[:len(L)//2]),
            merge_sort(L[len(L)//2:]))

Note: It is still possible to implement merge_sort using iteration but it is not easy!

The advantages of merge sort algorithm are:

• It runs much faster than the three sorting algorithm that i described above for large set of data. For example, if a list of n elements is given to be sorted, the running time complexity of  merge sort is consistently O(nlogn), independent on the state of the list. 
• It is a stable sorting algorithm.
• It can be implemented using recursion.

The disadvantages of merge sort:

• It's not easy to write especially if you don't know how to write recursive function! So it is not suitable for beginner. (That's why they skip it in CSC 108) 
• However since it use recursion, the algorithm take considerable stack memory. In fact, it take twice as much stack memory as quick sort.

Below is the model showing how the algorithm sort the list of 8 elements L = [4, 2, 7, 8, 5, 1, 6]. 

(Source: Aditya Dev Mishra, 2009, Selection Best Sorting Algorithm for a Particular Problem. Retrieved from:http://www.gdeepak.com/thesisme/Thesis-Selection%20of%20Best%20Sorting%20Algorithm%20for%20a%20Particular.pdf)

5. Quick sort: works based on the fact that it is easier to sort two small lists than the bigger one.  If a list of size n is given, the algorithm first check if n is less than 2. If n is less than 2, then the original list is return since a list with single element or blank list do not need to be sorted (the base case). When n>2, the algorithm will somehow pick a pivot value, the time complexity of quick sort is dependent on how well you pick this value. The value is later used as a pivot to split a given list into two sub lists. All of items that are less than pivot value are in the left sub list, whereas the items that are greater than pivot value are in the right sub list. The algorithm recursively split the sub-lists until it reaches the base case. Following is one implementation of quick sort in Python:

def quick1(L):
    if len(L) > 1:
        # Choose first element in list L as pivot value.
        pivot = L[0]
        # Any values that less that the pivot value go to the left sublist.
        smaller_than_pivot = [x for x in L[1:] if x < pivot]
        # Any values that are greater than pivot value go to the right sublist.
        larger_than_pivot = [x for x in L[1:] if x >= pivot]
        # Recursively quick sort the right and left sub lists then join them
        # together with the pivot value at the middle.
        return quick1(smaller_than_pivot) + [pivot] + quick1(larger_than_pivot)
    else: # base case: when len(L) < 2, the list L doesn't need to be sored.
        return L

The worst case time complexity of quick sort is T(n) = O(n²), quick sort though 99% performs at its best case running time, T(n) = Ω(nlog(n)). It is impossible to get rid of the worst case running time of quick sort, however we can increase the likelihood (up to 99.9999%) that the algorithm will have nlog(n) performance by doing one of the following three things:

1. Rather than alway using the left most or right most value in the list as pivot value, which causes the worst case running time when the list is already sorted, we randomly pick a pivot value in the list using built-in random class. 
2. Shuffle the list before picking a pivot value.
3. It is even better if you do both shuffling the list and randomly picking a pivot.

Optimized implementation for quick sort:

import random  
def quick2(L):
    if len(L) > 1:
        random.shuffle(L)
        pivot = random.choice(L)
        index = L.index(pivot)
        smaller_than_pivot = [L[i] for i in range(len(L[:])) if L[i] < pivot and i!=index]
        larger_than_pivot = [L[i] for i in range(len(L[:])) if L[i] >= pivot and i!=index]
        return quick2(smaller_than_pivot) + [pivot] + quick2(larger_than_pivot)
    else:
        return L

The advantages of using Quick Sort:

• Although the worst case running time of quick sort is O(n²), it has very efficient average running time of nlogn, making it the fastest sorting algorithm all of aforementioned sorting algorithms.
• Unlike merge sort,  recursive function of quick sort is very elegant and easy to understand. Moreover, there is no need to write helper function.

Quick Sort's only disadvantage:

• As i already mentioned, it is impossible to get rid of the worst case running time O(n²).

6. Count Sort: The professor did not mention much about this type of sort in the class, but for the completion of the slog, i want to mention it here. It is a linear sorting algorithm that sort element in O(n) time. The feature that make its unique from other sorting algorithms is that it sorts the elements without using any comparison operators!

Here is the professor Heap's algorithm for count sort:

def count_sort(L):
    count_list = [0, ] * (max(L) + 1)
    for i in L:
        count_list[i] += 1
    L1 = [] # blank slate!
    for i in range(len(count_list)):
        L1.extend([i]*count_list[i])  
    return L1

In his algorithm, he first created a temporary list named "count_list", this list was initialized to store only number 0, and the number of 0 in the "count_list" is equal to the maximum value in the given list L plus 1. For example, if L = [4, 1, 2] and max(L) = 4,  count_list = [0, 0, 0, 0, 0] len(count_list) = 5 = max(L) + 1.

Secondly, he then iterates through the given list, and increments any elements in count_list by 1 if its index is a value in the given list. So continue with our example above, we have L = [4, 1, 2], so all elements in count_list at index 4, 1, 2 are incremented by 1, count_list = [0, 1, 1, 0, 1, 0].

Thirdly, he loops through count_list using its length. If at any particular index, the item is 0, then he extends nothing into his returned list L1, [i]*0 = []. Otherwise, if the item is different from 0, the index of that item is added into L1. L1 in the example is [1, 2, 4].

Let look at one more example where the elements in given list is repeated.
L = [2, 3, 4, 2, 1]

Step 1: max(L) = 4 => count_list = [0, 0, 0, 0, 0, 0], len(count_list) = 6 = len(L) + 1
Step 2: L = [2, 3, 4, 2, 1] ==> count_list = [0, 1, 2, 1, 1, 0]. At this step, the value at index 2 in count_list is 2 because there are 2 2s in L.
Step3: Loop through count_list and starts to add elements into L1:

• count_list[0] = 0 => L1.extend([]) because [0]*0 = []
• count_list[1] = 1 => L1.extend([1] * 1)
• count_list[2] = 2 => L1.extend([2] * 2)
• count_list[3] = 1 => L1.extend([3] * 1)
• count_list[4] = 1 => L1.extend([4] * 1)
• count_list[5] = 0 => L1.extend([]) because [5]*0 = []

Now L1 = [1, 2, 2, 3, 4], the sort is finished!

The advantages of count_sort:

• It run very quick for any sets of data that have the values not so much greater than its length.

The disadvantages:

• Count sort can't be used to sort a list of string or nested list unless some mappings have been done. 
• Although count_sort gives a linear performance O(n), it become very inefficient when there is an extreme value in the list that is so much bigger than the length of the given list. 

One important conclusion that can be derived from count_sort is that algorithm with smaller big-O is not necessarily run faster than the other algorithms that have higher big O.

Fuuu! Finished, it is a very detailed analysis of different type of sorts according to my understanding so far. I don't think all of things i have written are right but I hope it is a good reflection on how good i am understanding the course material.

If you are TA, who is marking my Slog, i hope you will consider my remark request form in Markus by the end of the term. I have submitted the form about 1.5 months ago but yet heard anything from you. For the first assigned Slog, you gave me 25% and said that i missed the Slog, although i had written 3-4 paragraphs on Object Orientated programming...