User Tools

Site Tools


python:insertion_sort

INSERTION SORTING

31.08.2012

From wikipedia:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

  • Simple implementation
  • Efficient for (quite) small data sets
  • Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
  • More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
  • Stable; i.e., does not change the relative order of elements with equal keys
  • In-place; i.e., only requires a constant amount O(1) of additional memory space
  • Online; i.e., can sort a list as it receives it

#!/usr/bin/env python
#
# INSERTION SORT
#
# first element is considered sorted
# starting with the second until the end of the list, we consider each time a pivot (list[2->n])
# we compare each time the pivot with the left elements; if smaller, we move it one position to the left
# because the left list will always be ordered, we stop either when we hit the position 0, or when pivot is bigger than a left element
#
#
 
def run_insertion_sort(unsorted_list):
    for pos in range(1, len(unsorted_list)):
        pivot = unsorted_list[pos]
        left = pos - 1
 
        while left > -1 and pivot < unsorted_list[left]:
            unsorted_list[left + 1] = unsorted_list[left]
            left = left - 1    
 
        unsorted_list[left + 1] = pivot
 
    return unsorted_list
 
 
 
if __name__ == '__main__':
    entered_str_numbers = raw_input("Row with separated numbers by space (ENTER to finish): ")
    list_numbers = entered_str_numbers.split(" ")
 
    try:
        clean_list_numbers = []
        for d in list_numbers:
            clean_list_numbers.append(int(d))
    except ValueError:
        pass
 
    sorted_list_numbers = run_insertion_sort(clean_list_numbers)
 
    print "Unsorted: {0}".format(" ".join(map(str, clean_list_numbers)))    
    print "Sorted: {0}".format(" ".join(map(str, sorted_list_numbers)))

python/insertion_sort.txt · Last modified: 2013/03/16 17:41 (external edit)