Bubbelsortering

Bubbelsortering är den enklaste sorteringsalgoritmen att beskriva: jämför två grannar, byt plats på dem om de står i fel ordning, och upprepa. Den är långsam på långa listor, men varje steg är lätt att följa, vilket gör den till den klassiska första algoritmen att titta på.

Staplar med olika höjd som sorteras, med två grannar markerade för ett byte och de högsta staplarna redan på plats i slutet
Staplar med olika höjd som sorteras, med två grannar markerade för ett byte och de högsta staplarna redan på plats i slutet

Idén

Gå igenom listan från vänster till höger och titta på varje par grannar. Om det vänstra värdet är större än det högra byter du plats på dem. När du når slutet har det största värdet förts hela vägen till sista platsen, ungefär som en bubbla stiger till ytan. En sådan genomgång kallas ett varv. Upprepa varven tills listan är sorterad.

Ett exempel

Ta 5, 1, 4, 2, 8. Första varvet jämför 5 och 1 och byter plats på dem, sedan 5 och 4 (byte), 5 och 2 (byte) och 5 och 8 (inget byte): 1, 4, 2, 5, 8. 8:an står nu på sin slutliga plats. Andra varvet jämför 1 och 4 (inget byte), 4 och 2 (byte) och 4 och 5 (inget byte): 1, 2, 4, 5, 8. Tredje varvet gör inga byten alls, så listan är sorterad: 9 jämförelser och 4 byten.

Varför varje varv sätter ytterligare ett värde på plats

Under ett varv följer det hittills största värdet alltid med: när varvet når det flyttar varje jämförelse det ett steg till åt höger. Första varvet lägger alltså det största värdet sist, andra varvet det näst största precis före, och så vidare. Efter varv k ligger de sista k platserna fast, och nästa varv kan stanna ett steg tidigare. Därför blir varven kortare.

Byten är lika med inversioner

En inversion är ett par värden i fel ordning: ett större värde någonstans före ett mindre. Att byta plats på två grannar som står fel tar bort exakt en inversion och skapar ingen ny. Bubbelsortering gör därför exakt lika många byten som startlistan har inversioner, oavsett i vilken ordning jämförelserna kommer. En sorterad lista har inga; en omvänd lista med n värden har n(n − 1)/2, det högsta möjliga.

Tidigt stopp och kostnaden

Om ett helt varv inte gör några byten står alla grannar i ordning och listan är sorterad. Genom att kontrollera det kan bubbelsortering bli klar med en sorterad lista på ett enda varv med n − 1 jämförelser. I värsta fall behövs ändå n − 1 varv och n(n − 1)/2 jämförelser, och i genomsnitt är antalet byten n(n − 1)/4. Båda växer med n², så en dubbelt så lång lista gör sorteringen ungefär fyra gånger så lång.

Bubbelsortering är stabil: lika värden byter aldrig plats, så de behåller sin ordning. Den sorterar på plats utan extra minne. Insättningssortering har samma egenskaper och behöver oftast färre steg, och mergesort och quicksort tar tid proportionell mot n log n, vilket är betydligt mindre på långa listor.

Utforska den

Öppna appen och tryck på Spela, eller tryck på Steg för att gå en jämförelse i taget. De två värden som jämförs är markerade, ett byte visas i en egen färg och värden som redan står på plats blir gröna. Testa en omvänd lista för att se värsta fallet, en nästan sorterad för att se tidigt stopp avsluta sorteringen efter några varv, eller skriv in talen från exemplet ovan.

Ofta ställda frågor

Vilken tidskomplexitet har bubbelsortering?

O(n²) i värsta fall och i genomsnitt: upp till n(n − 1)/2 jämförelser för n värden. Med tidigt stopp tar en redan sorterad lista O(n), ett enda varv. Den behöver bara O(1) extra minne.

Är bubbelsortering stabil?

Ja. Den byter bara plats på två grannar när den vänstra är strikt större, så lika värden passerar aldrig varandra och behåller sin ursprungliga ordning.

Vad är skillnaden mellan bubbelsortering och insättningssortering?

Båda byter plats på grannar och båda gör lika många byten som det finns inversioner. Bubbelsortering gör hela varv över den osorterade delen; insättningssortering flyttar varje nytt värde bakåt bara så långt som behövs, så den gör oftast färre jämförelser, särskilt på nästan sorterade listor.

När är bubbelsortering ett bra val?

Mest i undervisning, och för mycket korta listor där enkelhet betyder mer än snabbhet. För allt större är den inbyggda sorteringen i ditt programmeringsspråk mycket snabbare.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Testa bubbelsortering