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)
Bubbelsort
Bubbelsort är en sortering som består av en yttre lopp som snurrar sålänge det behövs, dvs sålänge det finns element som behöver byta plats i listan.
Den inre loopen skannar hela listan från början till slut och om den hittar 2 element som står i fel ordning, så byter den plats på dessa.
sortering med bubblesort
Tidskomplexiteten för sortering med bubblesort är O(N2) då vi har 2 stycken loopar i varandra.
Algoritm
Konceptet här, det är att vi har en yttre loop som snurrar tills vidare och enbart avbryts (break) om listan är fullt sorterad. En inre loop som vänder på elementen parvis om de är i fel ordning. Anledningen till att den inre loopen måste utföras upprepade gånger, det är ju därför att varje gång ett felvänt par vänds rätt, så kan de fortfarande vara långt ifrån sin slutgiltiga plats i en sorterad lista.
yttre loop: oändlig
Vi har yttre en oändlig lopp som enbart bryts med break, ifall det inte längre finns några element som måste byta plats efter ett svep över hela listan.
inre loop
Den inre loppen skannar hela listan och byter plats på elementen parvis om de har fel inbördes ordning. För varje sådant här varv när hela listan gås igenom så kommer elementen sakta röra sig mot sin riktiga positioner och i slutändan finns det inte längre några element att byta plats på.
Medan visar 1 svep. För samtliga svep klicka på koden.
0
1
2
3
4
5
6
7
8
9
10
543
123
5
564
43
4
1233
12
3
1
4
123
543
5
564
43
4
1233
12
3
1
4
123
5
543
564
43
4
1233
12
3
1
4
123
5
543
43
564
4
1233
12
3
1
4
123
5
543
43
4
564
1233
12
3
1
4
123
5
543
43
4
564
1233
12
3
1
4
123
5
543
43
4
564
12
1233
3
1
4
123
5
543
43
4
564
12
3
1233
1
4
123
5
543
43
4
564
12
3
1
1233
4
123
5
543
43
4
564
12
3
1
4
1233
Om du klickar kör på nedan kod så ser du fullständig utskift. Notera att på slutet kommer den behöva köra igenom ett helt svep där den inte gör något alls. Flaggan byttplats förblir då falsk och den yttre loppen avbryts.
lista = [543,123,5,564,43,4,1233,12,3,1,4]
print(lista)
def bubbleSort(lst):
n = len (lst)
while(True):
byttplats = False
for i in range(1,n):
print(lst)
if lst[i-1] > lst[i]:
(lst[i],lst[i-1])=(lst[i-1],lst[i])
byttplats = True
if(not byttplats):
break
bubbleSort(lista)
print(lista)
lista = [543,123,5,564,43,4,1233,12,3,1,4]
print(lista)
def bubbleSort(lst):
n = len (lst)
while(True):
byttplats = False
for i in range(1,n):
print(lst)
if lst[i-1] > lst[i]:
(lst[i],lst[i-1])=(lst[i-1],lst[i])
byttplats = True
if(not byttplats):
break
bubbleSort(lista)
print(lista)
Nedan utan utskrifter.
lista = [543,123,5,564,43,4,1233,12,3,1,4]
print(lista)
def bubbleSort(lst):
n = len (lst)
while(True):
byttplats= False
for i in range(1,n):
if lst[i-1] > lst[i]:
(lst[i],lst[i-1])=(lst[i-1],lst[i])
byttplats= True
if(not byttplats):
break
bubbleSort(lista)
print(lista)
lista = [543,123,5,564,43,4,1233,12,3,1,4]
print(lista)
def bubbleSort(lst):
n = len (lst)
while(True):
byttplats= False
for i in range(1,n):
if lst[i-1] > lst[i]:
(lst[i],lst[i-1])=(lst[i-1],lst[i])
byttplats= True
if(not byttplats):
break
bubbleSort(lista)
print(lista)