How to Implement Insertion Sorting in Python

Through this example, we will get the methods to implement insertion sorting in Python.

Method

The idea of insertion sorting is very simple: insert the elements to be sorted into an ordered sequence. For example, the first element is treated as an ordered sequence, and elements are sequentially selected from the unordered sequence into the ordered sequence.

1. Suppose there is a set of unordered sequence R[0], R[1], …, R[N-1]. An element with the index of 0 is first treated as an ordered sequence.
2. Then insert R[1], R[2], …, R[N-1] into this ordered sequence. An external loop is required, scanning from index 1 to N-1.
3. Suppose you want to insert R[i] into the previously ordered sequence. When R[i] is inserted, you need to compare it to every element in the range (R[0] to R[i-1]) for determining the appropriate position to insert.

Source Code

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

def insertSort(arr):
    length = len(arr)
    for i in range(1,length):
        x = arr[i]
        for j in range(i,-1,-1):
            # J is the current position, and the j-1 position is tested
            if x < arr[j-1]:
                arr[j] = arr[j-1]
            else:
                # The position is j                        
                break
        arr[j] = x

def printArr(arr):
    for item in arr:
        print(item,end='t')

Length=int(input('Please input the num of elements'))

# input the list from terminal
List=[]
for i in range(Length):
    print('please input the %d element'%(i+1))
    tmp=int(input())
    List.append(tmp)
print(List)

insertSort(List)
printArr(List)

Output:

Please input the num of elements8
Please input the 1 element
11
Please input the 2 element
33
Please input the 3 element
145
Please input the 4 element
42
Please input the 5 element
89
Please input the 6 element
178
Please input the 7 element
3
Please input the 8 element
9
[11, 33, 145, 42, 89, 178, 3, 9]
3   9   11  33  42  89  145 178