Through this example, we will get the methods to implement insertion sorting in Python.
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.
- Suppose there is a set of unordered sequence R, R, …, R[N-1]. An element with the index of 0 is first treated as an ordered sequence.
- Then insert R, R, …, R[N-1] into this ordered sequence. An external loop is required, scanning from index 1 to N-1.
- 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 to R[i-1]) for determining the appropriate position to insert.
#! /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)
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