bubbelsortering

en enkel men ofta tidskrävande metod för att sortera. Bubbelsortering kan användas för att sortera tal i nummerordning, ord i bokstavsordning eller för annan sortering i en fastställd ordning (linjär ordning). – Bubbelsortering går till så att ett program går igenom talen (eller bokstäverna) i den ordning de är givna, från början till slut, två intilliggande tal i taget. De två första talen jämförs, och om det andra talet är lägre än det första låter programmet dem byta plats. Sedan jämför programmet det andra talet med det tredje talet på samma sätt, och så vidare tills programmet kommer till slutet av talserien. Då börjar proceduren om från början. Detta upprepas till programmet kan gå igenom hela talserien utan att göra en enda omflyttning. Då är talen ordnade i storleksordning (eller orden i bokstavsordning) och programmet avslutas. Exempel:

41352 > 14352 > 13452 > 13425 > (ny genomgång:) 13425 > 13245 > 12345> (slutliga genomgången:) 12345.

– När man ska sortera stora mängder är bubbelsortering tidskrävande jämfört med andra metoder, och det används nästan aldrig i praktiken. En nackdel är att programmet inte vet när mängden är sorterad, utan upptäcker det först när det kan gå igenom hela mängden utan att ändra något. Även om programmet bara behöver göra en enda omflyttning måste det ändå gå igenom hela talserien två gånger. – Vad som ofta gör bubbelsortering ineffektivt är att höga tal snabbt rör sig bakåt (alltså till sin rätta plats) i mängden, medan låga tal rör sig långsamt framåt – ett steg per genomgång. Höga tal tidigt i den ursprungliga talserien kallas därför för kaniner, låga tal långt bak i serien kallas för sköldpaddor. Ett enda lågt tal långt bak i den ursprungliga talserien kan göra att programkörningen tar många gånger längre tid än vad den annars skulle göra. – På engelska: bubble sort. – Benämningen syftar på att låga tal ”bubblar” upp till sin rätta plats. – Läs mer i Wikipedia.

[data] [ändrad 2 april 2020]

Dagens ord: 2020-04-02