Insertion sort is a simple sorting algorithm efficient for small datasets and for partially sorted lists. It builds a sorted list (array) of elements.

Best case time complexity is linear: O(n)

Worst case and average case time complexities are quadratic: O()

Following code is in Python2.7

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# !/usr/bin/python2.7 # -*- coding: utf-8 -*- """ Created on Thu January 15, 2015 @author: Vasanthi Vuppuluri Last Modified on: January 15, 2015 """ """ PURPOSE: -------- - To sort a list of integers using Insertion sorting technique - Requirements: Python 2.7 No additional module installations are required """ class InsertionSort: 'To sort a list of integers using Insertion sort' def __init__(self): print "Enter a series of numbers to be sorted seperated by a space:" self._input = raw_input() self._input_to_list = [int(_i) for _i in self._input.split()] # converts a string of numbers to list of integers print "List of numbers to be sorted: %s" %(self._input_to_list) def insertion_sort(self): _input_list = self._input_to_list L = len(_input_list) for _j in xrange(1,L): _key = _input_list[_j] _i = _j - 1 while (_i >= 0) and (_input_list[_i] > _key): _input_list[_i + 1] = _input_list[_i] _i = _i - 1 _input_list[_i + 1] = _key print "\t", _input_list return _input_list sort = InsertionSort() _sorted_list = sort.insertion_sort() print "Sorted list: %s" %(_sorted_list) |

## Leave a Reply