Algorithm: Insertion Sort

Algorithm

https://www.w3resource.com/php-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-3.php
https://www.w3resource.com/php-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-3.php

Comparison with bubble sort

It is actually very similar to bubble sort. The only difference is

  • Bubble down to the left end

Characteristics

  • O(n²)

Implementation

python

def insertionsort(list):
for i in range(len(list)):
current = list[i]
j = i-1
while j>= 0 and current < list[j]:
list[j], list[j+1] = list[j+1], list[j]
j = j-1
return list
list = [9,8,7,6,5,4,3,2,1]
print(insertionsort(list))
def insertionsort(list):
for i in range(len(list)):
current = list[i]
j = i-1
while j>= 0 and current < list[j]:
temp = list[j]
list[j] = list[j+1]
list[j+1] = temp
j = j-1
return list
list = [9,8,7,6,5,4,3,2,1]
print(insertionsort(list))

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store