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.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- ja
- ja
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
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.