Insertion Sort and Shell Sort – the two brothers

A good explanation of insertion sort can be found over here:

I personally like this video a lot:

itemList = [4,28,56,3,89,90,126]

def insertion_sort(itemList):
    for i in range(1,len(itemList)):
        value = itemList[i]
        j = i
        while (j-1 >= 0 and value < itemList[j-1]):
            itemList[j]=itemList[j-1]
            j-=1
            
        itemList[j] = value
    return itemList

print insertion_sort(itemList)

You can find a similar video for shell sort:

def shell_sort(itemList):
    
    gap = len(itemList)//2
    
    while (gap > 0):
        for i in range(gap,len(itemList)):
            value = itemList[i]
            j = i
            while (j-gap >= 0 and value < itemList[j-gap]):
                itemList[j] = itemList[j-gap]
                j -= gap
            itemList[j] = value
        gap //= 2
        
    return itemList
        
        
print shell_sort(itemList)

Advertisement