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(N²) 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.

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.

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.

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.

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(n²)

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.

Nedan utan utskrifter.