# Goodies Lemonsoftare

### Site Tools

python:insertion_sort

# Differences

This shows you the differences between two versions of the page.

 python:insertion_sort [2013/03/16 17:41] python:insertion_sort [2013/03/16 17:41] (current) Line 1: Line 1: + ==== INSERTION SORTING ==== + 31.08.2012 + + From [[http://​en.wikipedia.org/​wiki/​Insertion_sort | 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 [[python:​merge_sort|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))) + 