Insertion sort-Python implementation

Insertion sort-Python implementation

Like it and then read it, get into a habit, search on WeChat [Haige python] to follow this Internet tool man.

principle

One sentence summary: select one data to be sorted one by one, and insert it into the sequence that has been sorted before.

1. Start from the second data of the array and compare it forward, that is, compare the second number with the previous one. If the conditions are met (larger or smaller than the previous one, custom), let them exchange positions.

2. Then use the third number to compare with the second one. If it matches, the exchange will be done. But here you have to continue to compare. For example, there are 5 numbers 8, 15, 20, 45, 17, 17 are smaller than 45, you need Exchange, but 17 is also smaller than 20, so it must be exchanged. When there is no need to exchange with 15, it means that there is no need to compare with the data before 15. There is definitely no need to exchange, because the previous data are all in order.

3. Repeat step two until all the data are arranged.

Diagram

performance

The time complexity is O(N^2), and the space complexity is O(1). The algorithm is stable, and both the number of comparisons and the number of exchanges are related to the initial sequence.

optimization

Direct insertion sorting is to search forwards in order each time it is inserted forward. You can optimize it here. When looking for a suitable insertion position forward, the binary search method is used, that is, half insertion (binary search insertion). Compared with the direct insertion sort: the average performance is faster, the time complexity is reduced to O(NlogN), and the sort is stable, but the number of comparisons of the sort has nothing to do with the initial sequence, and always requires foor(log(i)) +1 sort comparison.

scenes to be used

When the data is basically in order, the use of insertion sort can significantly reduce the number of data exchanges and data movements, thereby improving the sorting efficiency.

The algorithm is suitable for sorting a small amount of data.

  • Direct insertion sort
def insertsort(mylist):
    length = len(mylist)
    if length <= 1:
        return mylist
    
    #  1 i i i-1 
    for i in range(1, length):
        j = i - 1
        #  
        if mylist[i] < mylist[j]:
            tmp = mylist[i]
            mylist[i] = mylist[j]
            
            #  tmp tmp 
            j -= 1
            while j >= 0 and tmp < mylist[j]:
                mylist[j+1] = mylist[j]
                j -= 1
            
            mylist[j+1] = tmp
    return mylist
        
mylist = [48, 38, 65, 97, 76, 13, 27, 49]
print(insertsort(mylist))
 
def insert_sort(lists):
    count = len(lists)
    if length <= 1:
        return mylist
    
    for i in range(1, count):
        #  
        key = lists[i]
        j = i - 1
        while j >= 0:
            #  
            if lists[j] > key:
                lists[j + 1], lists[j] = lists[j], key
            j -= 1
    return lists
        
mylist = [48, 38, 65, 97, 76, 13, 27, 49]
print(insert_sort(mylist))
 
  • Half Insertion Sort

    Insert a new element in a set of ordinal numbers and find out whether the insertion position is the upper half or the lower half

 # -*- coding:utf-8 -*-

def binaryInsert(series,a):
	for i in range(0,len(series)):
		low = 0
		high = len(a) - 1
		m = (low + high)//2
		while low < high:
			if a[m] > series[i]:
				high = m - 1
			elif a[m] < series[i]:
				low = m + 1
			else:
				high = m
			m = (low + high)//2
		a.insert(high+1,series[i])
a = []
l = [3,78,7,90,19,21,2,36,66]
binaryInsert(l,a)
print(a)