Insertion sort

I have enrolled for advanced computer algorithm course in winter fall 2013. As a part of required reading, we were asked to understand how the insertion sort works. In the write-up, I will be explaining how does the algorithm works and will provide you a python code of the same.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Lets see an example:

Input list:

5 6 3 1 8 7 2 4

While processing:

5 6 3 1 8 7 2 4
5 6 3 1 8 7 2 4

3 5 6 1 8 7 2 4

1 3 5 6 8 7 2 4

1 3 5 6 8 7 2 4

1 3 5 6 7 8 2 4

1 2 3 5 6 7 8 4

1 2 3 4 5 6 7 8

So the sorted list looks like this:

1 2 3 4 5 6 7 8
# /usr/bin/python
# A program to do insertion sort

def insertion_sort(inp_list):
    '''Insertion sort function'''

    for i in range(1, len(inp_list)): # => C*n operations, given n is the no of elements in the list
        valueToInsert=inp_list[i]     # => C*(n-1) operations                          
        holePos=i                     # => C*(n-1) operations
        '''The current index is cached in-order to look if the valueToInsert is less
        than the elements in the sorted list.'''
        while holePos > 0 and valueToInsert  C *(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
            ''' i time(s) is checked whether the valueToInsert is less than the elements
            in the sorted list.'''
            inp_list[holePos] = inp_list[holePos - 1]  # => C*(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
            holePos = holePos -1                       # => C*(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
        inp_list[holePos] = valueToInsert              # => C*(n-1) operations
    return inp_list

def main():
    '''Main function'''

    inp =[]
    s = int(raw_input('How many elements would you like to enter: '))
    for x in range(s):
        inp.append(int(raw_input('Enter element #' + `x+1` + ': ')))
    output_list = insertion_sort(inp) 
    print "Sorted list: ", output_list

if __name__ == "__main__":
    main()

Best case (If the list is already sorted complexity becomes): O(n)
Worst case (If the list is sorted in the descending order): O(C *(n-1)*\latex{\sum\limits_{i=0}^n i}) = O(n^2)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s