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)

One thought on “Insertion Sort and Shell Sort – the two brothers

  1. Pingback: Introduction to Data Structures and Algorithms | codeatsociallywired

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s