User Tools

Site Tools


python:insertion_sort

Differences

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

Link to this comparison view

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
 +
 +
 +<code python>
 +#​!/​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)))
 +</​code>​
  
python/insertion_sort.txt ยท Last modified: 2013/03/16 17:41 (external edit)