Steg 0 / 0 · Jämförelser: 0 · Byten: 0
Så fungerar algoritmen
Så fungerar den
- Börja med en osorterad array av tal.
- Jämför de två första intilliggande elementen.
- Om det vänstra elementet är större än det högra, byt plats på dem.
- Gå vidare till nästa par och upprepa.
- Efter en hel genomgång har det största elementet 'bubblat' till slutet.
- Upprepa processen för den återstående osorterade delen.
- Om en genomgång slutförs utan byten är arrayen sorterad.
Nyckelbegrepp
- Jämförelsebaserad sortering
- Stabil sortering (bevarar inbördes ordning för lika element)
- På plats (O(1) extra minne)
- Adaptiv: bästa fallet O(n) med tidigt avbrott
När den passar
När indata är liten eller nästan sorterad. Används sällan i praktiken för stora datamängder på grund av komplexiteten O(n^2) i genomsnittsfallet.
Visste du
Bubble sort kallas ibland 'sinking sort' eftersom större element 'sjunker' till botten.