Algorithm: Insertion Sort
Dec 29, 2020
Another inefficient algorithm to remember for your interview question (maybe?)
Algorithm
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 listlist = [9,8,7,6,5,4,3,2,1]
print(insertionsort(list))
c++
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 listlist = [9,8,7,6,5,4,3,2,1]
print(insertionsort(list))
