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 består av 2 loopar i varandra. Den inre loopen går igenom listan och jämför talen parvis och om det är nödvändigt byter den plats på värden, parvis. Den yttre loopen snurrar sålänge den inre loopen måste byta plats på värden. Dvs, sålänge listan inte är färdigsorterad.
sortering med bubblesort
Tidskomplexiteten för sortering med bubblesort är O(N2) då vi har 2 stycken loopar i varandra.
Sortering i sin enklaste form
Om man sitter och labbar förutsättningslöst utan att veta något om sortering, så är det troligtvis så att det är bubble-sort är det man skulle uppfinna. Låt oss ta en liten omväg för att du verkligen ska komma in i sortering och komplexitet och få en hint om varför det heter bubblesort.
Säg att vi har en lista av osorterade tal.
0
1
2
3
4
5
6
7
8
9
10
543
123
5
564
43
4
1233
12
3
1
4
Säg nu att vi vill sortera dessa tal. Vad innebär det att sortera? Det innebär att vi grupperar om talen, flyttar om talen, så att de ligger i storleksordning. Vi betraktar talen i par om 2 stycken och låter talen byta plats om nödvändigt.
Låt oss skapa en loop som printar ut listan. Vi kan förstås använda print() men vi vill börja koda en sorteringsfunktion, så vi börjar såhär istället.
lista = [543,123,5,564,43,4,1233,12,3,1,4]
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
lista = [543,123,5,564,43,4,1233,12,3,1,4]
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
Vilken komplexitet har föresten ovan snurra? O(n) såklart. Det är en vanlig hederlig loop.
Vi vill nu, i vår loop ovan, jämföra talen som står sida vid sida med varandra. Om det senare är mindre än det tidigare, då byter vi plats på talen eftersom de står i fel ordning. Vi printar listan före och efter vi gjort detta.
lista = [543,123,5,564,43,4,1233,12,3,1,4]
print("listan innan")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
print()
i = 0
while( i < len(lista)):
if(lista[i] < lista[i-1]):
(lista[i],lista[i-1])=(lista[i-1],lista[i])
i+=1
print("listan efter")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
lista = [543,123,5,564,43,4,1233,12,3,1,4]
print("listan innan")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
print()
i = 0
while( i < len(lista)):
if(lista[i] < lista[i-1]):
(lista[i],lista[i-1])=(lista[i-1],lista[i])
i+=1
print("listan efter")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
Vad händer här? Det som händer är att listan är pyttelite mer i ordning, kan man säga. Stora tal som står fel, de bubblar upp på högre positioner. Stora tal kan bubbla upp flera positioner, ser det ut som. Det blir ju så eftersom talen byter plats parvis inne i loopen, så det flyttar upp ett steg i varje loop-varv, med lite tur.
Titta på nedan illustration, där vi ser hur listan utvecklas för varje varv i loopen. Vi jämför talen parvis (rosa), det är ju det vi gör med jämförelsen lista[i] < lista[i-1]. Om vi måste byta plats på dem, då gör vi det. Försäkra dig om att du förstår.
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
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 det enbart var något enstaka stort tal som skulle flyttas upp, då hade det räckt med en enda loop.
Men låt säga att det ser ut såhär, worst-case.
lista = [13,12,11,10,9,8,7,6,5,4,3,2,1]
print("listan innan")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
print()
i = 0
while( i < len(lista)):
if(lista[i] < lista[i-1]):
(lista[i],lista[i-1])=(lista[i-1],lista[i])
i+=1
print("listan efter")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
lista = [13,12,11,10,9,8,7,6,5,4,3,2,1]
print("listan innan")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
print()
i = 0
while( i < len(lista)):
if(lista[i] < lista[i-1]):
(lista[i],lista[i-1])=(lista[i-1],lista[i])
i+=1
print("listan efter")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
Det vi ser är att worst-case flyttas tal 1 position närmare sin riktiga plats. Så om vi körde vår jämförelse 2 gånger, flyttas tal 2 positioner närmare sin plats.
lista = [13,12,11,10,9,8,7,6,5,4,3,2,1]
print("listan innan")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
print()
i = 0
while( i < len(lista)):
if(lista[i] < lista[i-1]):
(lista[i],lista[i-1])=(lista[i-1],lista[i])
i+=1
i = 0
while( i < len(lista)):
if(lista[i] < lista[i-1]):
(lista[i],lista[i-1])=(lista[i-1],lista[i])
i+=1
print("listan efter")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
lista = [13,12,11,10,9,8,7,6,5,4,3,2,1]
print("listan innan")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
print()
i = 0
while( i < len(lista)):
if(lista[i] < lista[i-1]):
(lista[i],lista[i-1])=(lista[i-1],lista[i])
i+=1
i = 0
while( i < len(lista)):
if(lista[i] < lista[i-1]):
(lista[i],lista[i-1])=(lista[i-1],lista[i])
i+=1
print("listan efter")
i = 0
while( i < len(lista)):
print(lista[i], end=":")
i+=1
Vi begriper att för att sorteringen verkligen skall sortera hela listan, så måste vi (1) jämföra talen parvis och eventuellt byta plats på dem vilket kommer bli en hel loop. Dessutom måste vi göra (1) lika många gånger som det finns tal i listan, worst-case, eftersom loopen (1) worst-case bara flyttar tal 1 position närmare sin plats.
Så, vi får en loop inuti en loop. Därför är också komplexiteten O(n2)
Nu går det optimera denna algoritm lite, förstår man snart. T.ex. kan vi avbryta om listan är färdigsorterad eftersom det då inte längre händer något när vi går igenom vår lista och jämför talen parvis. Om de redan ligger rätt, så kommer vi gå igenom listan utan att något händer och det tar bara tid. Så vi kan avbryta om inga tal behöver byta plats parvis.
Algoritm bubblesort
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)