Teaching Kids Programming – Insertion Sort in Python (Simple Sorting Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Insertion sort is another simple sorting algorithm. It works by inserting a current element into the right place of the front partially sorted sub array.

Insertion Sort Implementation in Python

We need to iterate n-1 times, we skip the first element as we can start a partially sorted array with first element. Then, we need to find a place to insert a current element. We can do this by comparing the previous numbers and shift/squeeze as the key (current numbers) is smaller.

1
2
3
4
5
6
7
8
9
10

def insertionSort(nums):
    n = len(nums)
    for i in range(1, n):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
                nums[j + 1] = nums[j]
                j -= 1
        nums[j + 1] = key
    return nums

def insertionSort(nums):
    n = len(nums)
    for i in range(1, n):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
                nums[j + 1] = nums[j]
                j -= 1
        nums[j + 1] = key
    return nums

If the array is already sorted, the inner while loop will not be entered and thus the time complexity is O(N). The average and worst cases time complexity is O(N^2) similar to other two simple sorting algorithms: bubble sorting and selection sort.

The insertion sorting algorithm is stable (the numbers of same values are preserved the order of they appearing).

Sorting Algorithms (Teaching Kids Programming Tutorials)

• Teaching Kids Programming – Bubble Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – MergeSort Simply Explained
• Teaching Kids Programming – QuickSort Algorithm Simply Explained
• Teaching Kids Programming – Selection Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – Insertion Sort in Python (Simple Sorting Algorithm)
• Teaching Kids Programming – Counting Sort Algorithm in Python

–EOF (The Ultimate Computing & Technology Blog) —