Detta skapar en PDF som du sedan kan skriva ut. Du kan även spara ner PDFn och skriva ut senare.
Titel på utskriften?
Tack för ditt bidrag
Om vi kan använda det så lägger vi upp det på sidan. Nedan en länk till ditt bidrag om du vill spara det.
Spara som ...
Du sparar ditt skript under detta namn och kan sedan hämta tillbaka det med samma namn.
Läs in
Läs in ett tidigare sparat skript. Obs att du enbart kan läsa in skript i den webbläsare där du sparade skriptet. Vill du kunna läsa in och spara skript oberoende av webbläsare, så behöver du skaffa ett login (enkelt och gratis).
Skicka in bidrag
Föreslå rubrik
Beskriv vad din kod gör
Skapa kort länk
Använd en kort URL för att skicka länk till koden via SMS eller epost. När mottagaren klickar på länken, så öppnas denna webbsida, med din kod och din text. Länken rensas bort automatiskt om den inte används.
Rubrik (frivilligt)
Beskrivning (frivilligt)
Länk (kopiera hela)
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 insertsort
Sortering med insertsort bygger på en algoritm med 2 loopar i varandra. Vi låter index för den yttre loopen vara i och index för den inre loopen vara j. Ok?
Yttre loop, i=1
Så, om vi startar någonstans, förslagsvis kan i vara 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
Den inre loopen startar med att 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)
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)
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)
Algoritmen 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)
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)
Hur ska du lära dig?
Hur ska du lära dig detta? Gör såhär: Plocka upp kodeditorn. Skapa en lista av tal. Skapa en loop som printar ut talen i listan. Skapa sedan en loop inuti loopen som vänder på talen parvis om de står fel.