Insertion Sort in Python3

Below is an example of the Insertion Sort algorithm in Python3. See the Insertion Sort page for more information and implementations.


insertion-sort in Python3

def insertion_sort(array):
    # start at the first index and iterate through to the end
    i = 1
    while(i < len(array)):
        currentIndex = i
        # Check:
        #      1. that currentIndex is at least 1
        #      2. that the item directly before the currentIndex is greater than the item at currentIndex
        #
        # If both conditions are met, swap the indexes
        while (currentIndex > 0 and array[currentIndex - 1] > array[currentIndex]):
            temp = array[currentIndex]
            array[currentIndex] = array[currentIndex - 1]
            array[currentIndex - 1] = temp
            currentIndex -= 1
        i += 1

if __name__ == '__main__':
    array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
    insertion_sort(array)
    print(array)

Discussion