Search
 
SCRIPT & CODE EXAMPLE
 
CODE EXAMPLE FOR PYTHON

How to perform insertion sort, in Python?

"""
This is an implementation of the insertion sort
algorithm. 
Idea is to grow a sorted subset from one element
and then pull all elements of array into that
sorted subset while keeping that subset sorted.
Let n be the size of the list to sort

Time complexity: O(n^2), 
Space complexity: O(1)
"""
def insertion_sort(arr):
    for idx in range(1, len(arr)):
        scan = idx
        while scan > 0 and arr[scan] < arr[scan-1]:
            swap(arr, scan, scan-1)
            scan -= 1
    return arr

def swap(arr, idx1, idx2):
    arr[idx1], arr[idx2] = arr[idx2], arr[idx1]

arr_to_sort = [1, 10, 3, 2]
print(insertion_sort(arr_to_sort))  # [1, 2, 3, 10]
 
PREVIOUS NEXT
Tagged: #How #perform #insertion
ADD COMMENT
Topic
Name
1+5 =