insertion_sort.py

"""
# Insertion Sort
"""
from search.binary_insert import binary_insert_right

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        curr = arr[i]
        j = i
        while j > 0 and arr[j-1] > curr:  # shift all greater elements (no swapping)
            arr[j] = arr[j-1]
            j -= 1
        arr[j] = curr  # insert current element
    return arr



def binary_insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        curr = arr[i]
        j = binary_insert_right(arr, curr, 0, i)  # O(log n), better when comparisons are expensive
        arr[j+1:i+1] = arr[j:i]    # O(n), but is a single call to C
        arr[j] = curr
    return arr



if __name__ == '__main__':
    from utils import test, plot_time_complexity
    test(insertion_sort([2, 1]), [1, 2])
    test(insertion_sort([1, 1]), [1, 1])
    test(insertion_sort([1, 2]), [1, 2])
    test(insertion_sort([1, 1, 2, 2, 3, 3]), [1, 1, 2, 2, 3, 3])
    test(insertion_sort([1, 2, 4, 3, 5, 6]), [1, 2, 3, 4, 5, 6])
    test(insertion_sort([2, 1, 2, 1, 2, 1]), [1, 1, 1, 2, 2, 3])
    test(insertion_sort([0, -1, 1, 0, -2, 2]), [-2, -1, 0, 0, 1, 2])
    test(insertion_sort([10 ** 9, -10 ** 9, 0, 5, -7]), [-10 ** 9, -7, 0, 5, 10 ** 9])
    test(insertion_sort([3.0, -0.0, 2.5, 2, 1.1]), [-0.0, 1.1, 2, 2.5, 3.0])
    test(insertion_sort([5, 4, 4, 3, 2, 1, 1]), [1, 1, 2, 3, 4, 4, 5])
    test(insertion_sort([1, 2, 3, 4, 5]), [1, 2, 3, 4, 5])
    test(insertion_sort([]), [])
    test(insertion_sort([1]), [1])
    test(insertion_sort(list(range(100, -1, -1))), list(range(0, 101)))
    plot_time_complexity(insertion_sort, lambda n: list(reversed(range(n))))