Skip to content

Instantly share code, notes, and snippets.

@luckylittle
Last active May 12, 2018 09:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save luckylittle/f587fc41860414b7b891ca3e69145d48 to your computer and use it in GitHub Desktop.
Save luckylittle/f587fc41860414b7b891ca3e69145d48 to your computer and use it in GitHub Desktop.
Insertion sort algorithm in Python
def insertion_sort(list):
"""
Insertion sort algorithm by @luckylittle
"""
for i in range(1, len(list)):
current = list[i]
while (i > 0) and (list[i-1] > current):
list[i] = list[i - 1]
i -= 1
list[i] = current
return list
test = [2, 5, 7, 1, 6, 9, 8] # Length = 7
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 4 5 6
print(insertion_sort(test))
# 1st pass = [2, 5, 1, 7, 6, 9, 8]
# 2nd pass = [2, 1, 5, 7, 6, 9, 8]
# 3rd pass = [1, 2, 5, 7, 6, 9, 8]
# 4th pass = [1, 2, 5, 6, 7, 9, 8]
# 5th pass = [1, 2, 5, 6, 7, 8, 9]
# How does it work exactly?
# First pass
# [2, 5, 7, 1, 6, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 <3 4 5 6
# i=1 , current=5
# i=2 , current=7
# i=3 , current=1
# i=3 , list[3]=1
# i=3 , list[2]=7
# i=2
# i=2 , list[2]=1
# [2, 5, 1, 7, 6, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 4 5 6
# Second pass
# [2, 5, 1, 7, 6, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 <2 3 4 5 6
# i=2 , list[2]=1
# i=2 , list[1]=5
# i=1
# i=1 , list[1]=1
# [2, 1, 5, 7, 6, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 4 5 6
# Third pass
# [2, 1, 5, 7, 6, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 <1 2 3 4 5 6
# i=1 , list[1]=1
# i=1 , list[0]=2
# i=0
# i=0 , list[0]=1
# [1, 2, 5, 7, 6, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 4 5 6
# Fourth pass
# [1, 2, 5, 7, 6, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 <4 5 6
# i=4 , current=6
# i=4 , list[4]=6
# i=4 , list[3]=7
# i=3
# i=3 , list[3]=6
# [1, 2, 5, 6, 7, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 4 5 6
# Fifth pass
# [1, 2, 5, 6, 7, 9, 8]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 4 5 <6
# i=5 , current=9
# i=6 , current=8
# i=6 , list[6]=8
# i=6 , list[5]=9
# i=5
# i=5 , list[5]=8
# [1, 2, 5, 6, 7, 8, 9]
# ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 4 5 6
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment