Bubbelsortering
Går igenom listan om och om igen och byter plats på grannar som ligger i fel ordning. Efter varje genomgång ligger det största kvarvarande värdet sist.
- bästa fall Ω(n)
- genomsnitt Θ(n²)
- värsta fall O(n²)
- minne O(1)
- stabil
- utan extra minne
Vad betyder det här?
- Bästa fall: hur tiden växer med listans storlek n när indata är den lättaste för den här algoritmen.
- Genomsnitt: hur tiden brukar växa med n. Med n² tar dubbla antalet värden ungefär fyra gånger så lång tid. n log n växer mycket långsammare.
- Värsta fall: tillväxten på den svåraste indatan. Viktigt när hastigheten aldrig får sjunka.
- Minne: hur mycket extra minne som behövs utöver listan. 1 betyder några variabler, n betyder en kopia av listan.
- Stabil: två lika värden behåller sin ursprungliga ordning. Viktigt när man sorterar poster efter ett fält.
- Utan extra minne: sorterar inuti själva listan, utan en andra lista.
- jämförs
- flyttas
- på slutgiltig plats
Tryck på Spela upp: linjerna visar hur kostnaden växer
Tryck på Spela upp eller gå igenom algoritmen steg för steg.
Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.
Prova det här: Välj en nästan sorterad lista. Efter en genomgång utan byten slutar algoritmen tidigt.
Så fungerar det
Den jämför två grannar i taget och byter plats på dem om den vänstra är större. Så flyttas det största värdet hela vägen till höger i varje genomgång, som en bubbla som stiger. Blir det inga byten under en genomgång är listan redan sorterad.
När det är ett bra val
Nästan aldrig i riktiga program, eftersom den är långsam på långa listor. Men den är perfekt att lära sig av: den visar grundidén att sortera genom att jämföra och byta. Den är snabb bara när listan redan är sorterad.