Start | insert sort
 

Insert sort



Insert sort är en sortering som bygger på en yttre loop som beaktar en allt större mängd av listan, med start från de 2 första elementen.

En inre loop vänder sedan om nödvändigt elementen parvis så att ordningen blir rätt.

sortering med insertsort

Om man använder insertsort för sortering får man leva med tidskomplexiteten O(N2) eftersom vi har 2 stycken loopar i varandra.

Algoritm

Sortering med insertsort bygger på en algoritm med 2 loopar i varandra.

Yttre loop, i=1



0 1 2 3 4 5 6 7 8 9 10
543 123 5 564 43 4 1233 12 3 1 4

Inre loop, j=1



0 1 2 3 4 5 6 7 8 9 10
543 123 5 564 43 4 1233 12 3 1 4

Är lista[j-1] > lista[j] ? Dvs är lista[0] > lista[1], isåfall byt plats på dessa.
0 1 2 3 4 5 6 7 8 9 10
123 543 5 564 43 4 1233 12 3 1 4


Yttre loop, i=2



0 1 2 3 4 5 6 7 8 9 10
123 543 5 564 43 4 1233 12 3 1 4

Inre loop, j=2



0 1 2 3 4 5 6 7 8 9 10
123 543 5 564 43 4 1233 12 3 1 4

Är lista[j-1] > lista[j] ? Dvs är lista[1] > lista[2], isåfall byt plats på dessa.

Inre loop, j=1




0 1 2 3 4 5 6 7 8 9 10
123 5 543 564 43 4 1233 12 3 1 4

Är lista[j-1] > lista[j] ? Dvs är lista[0] > lista[1], isåfall byt plats på dessa.

0 1 2 3 4 5 6 7 8 9 10
5 123 543 564 43 4 1233 12 3 1 4

Yttre loop, i=3



0 1 2 3 4 5 6 7 8 9 10
5 123 543 564 43 4 1233 12 3 1 4

Yttre loop, i=4



0 1 2 3 4 5 6 7 8 9 10
5 123 543 564 43 4 1233 12 3 1 4

Inre loop, j=4



0 1 2 3 4 5 6 7 8 9 10
5 123 543 564 43 4 1233 12 3 1 4

Är lista[j-1] > lista[j] ? Dvs är lista[0] > lista[1], isåfall byt plats på dessa.

Inre loop, j=3



0 1 2 3 4 5 6 7 8 9 10
5 123 543 43 564 4 1233 12 3 1 4

Är lista[j-1] > lista[j] ? Dvs är lista[0] > lista[1], isåfall byt plats på dessa.

Inre loop, j=2



0 1 2 3 4 5 6 7 8 9 10
5 123 43 543 564 4 1233 12 3 1 4

Är lista[j-1] > lista[j] ? Dvs är lista[0] > lista[1], isåfall byt plats på dessa.

Inre loop, j=1



0 1 2 3 4 5 6 7 8 9 10
5 43 123 543 564 4 1233 12 3 1 4

Är lista[j-1] > lista[j] ? Dvs är lista[0] > lista[1], isåfall byt plats på dessa.

0 1 2 3 4 5 6 7 8 9 10
5 43 123 543 564 4 1233 12 3 1 4


Såhär fortsätter algoritmen till den yttre loopen kommit tilllängden av listan.
lista = [543,123,5,564,43,4,1233,12,3,1,4] print(lista) i = 1 while( i < len(lista)): j=i while j > 0 and lista[j-1] > lista[j]: print(lista) (lista[j],lista[j-1])=(lista[j-1],lista[j]) j = j -1 i = i + 1 print(lista)
Nedan utan utskrifter.
lista = [543,123,5,564,43,4,1233,12,3,1,4] print(lista) i = 1 while( i < len(lista)): j=i while j > 0 and lista[j-1] > lista[j]: (lista[j],lista[j-1])=(lista[j-1],lista[j]) j = j -1 i = i + 1 print(lista)
Algopritmen går också att implementera i en rekursiv version.
lista = [543,123,5,564,43,4,1233,12,3,1,4] print(lista) def insertionSortR(lst, n): if n > 0: insertionSortR(lst, n-1) x = lst[n] j = n-1 while j >= 0 and lst[j] > x: lst[j+1] = lst[j] j = j-1 lst[j+1] = x insertionSortR(lista, len(lista)-1) print(lista)
Den rekursiva algoritmen gör varken koden kortare eller snabbare (samma komplexitet), men den ökar minnesåtgången från O(1) till O(N)
15.111207962036 ms