Boblesortering (Norsk)
Et eksempel på boblesortering. Begynn fra begynnelsen av listen, sammenlign hvert tilstøtende par, bytt posisjon hvis de ikke er i riktig rekkefølge (sistnevnte er mindre enn det tidligere). Etter hver iterasjon er det nødvendig å sammenligne ett mindre element (det siste) til det ikke er flere elementer igjen å sammenligne.
PerformanceEdit
Boblesortering har en worst-case og gjennomsnittlig kompleksitet på О (n2), der n er antall elementer som blir sortert. De fleste praktiske sorteringsalgoritmer har betydelig bedre verste fall eller gjennomsnittlig kompleksitet, ofte O (n log n). Selv andre О (n2) sorteringsalgoritmer, for eksempel innsettingssortering, går vanligvis raskere enn boblesortering, og er ikke mer komplekse. Derfor er boblesortering ikke en praktisk sorteringsalgoritme.
Den eneste betydelige fordelen som boblesortering har over de fleste andre algoritmer, til og med kviksort, men ikke innsettingssorter, er at muligheten til å oppdage at listen er sortert effektivt er innebygd i algoritmen. Når listen allerede er sortert (best-case), er kompleksiteten til boblesortering bare O (n). Derimot utfører de fleste andre algoritmer, til og med de med bedre kompleksitet i gjennomsnitt, hele sin sorteringsprosess på settet og er dermed mer komplekse. Imidlertid deler ikke innsettingssortering denne fordelen, men den fungerer også bedre på en liste som er vesentlig sortert (med et lite antall inversjoner). I tillegg, hvis denne oppførselen er ønsket, kan den legges trivielt til en hvilken som helst annen algoritme ved å sjekke listen før algoritmen kjører.
Boble-sortering bør unngås i tilfelle store samlinger. Det vil ikke være effektivt når det gjelder en omvendt ordnet samling.
Rabbits and TurtlesEdit
Avstanden og retningen elementene må bevege seg under sorten, bestemmer ytelsen til boblesorteringen elementer beveger seg i forskjellige retninger med forskjellige hastigheter. Et element som må bevege seg mot slutten av listen, kan bevege seg raskt fordi det kan delta i suksessive bytter. For eksempel vil det største elementet i listen vinne hver bytte, så det beveger seg til sin sorterte posisjon ved første pass, selv om den begynner nær begynnelsen. På den annen side kan et element som må bevege seg mot begynnelsen av listen ikke bevege seg raskere enn ett trinn per pass, så elementene beveger seg mot begynnelsen veldig sakte. det minste elementet er på slutten av listen, vil det ta n − 1 pass for å flytte det til begynnelsen. Dette har ført til at disse typene elementer har blitt kalt henholdsvis kaniner og skilpadder, etter tegnene i Esops fabel av Skilpadden og haren.
Ulike det er gjort forsøk på å eliminere skilpadder for å forbedre hastigheten på boblesorteringen. Cocktailsortering er en toveis boblesortering som går fra begynnelse til slutt, og deretter reverserer seg selv, går ende til begynnelse. Den kan flytte skilpadder ganske bra, men den beholder O (n2) worst-case kompleksitet. Kamsortering sammenligner elementer skilt med store hull, og kan flytte skilpadder ekstremt raskt før du fortsetter til mindre og mindre hull for å glatte ut listen. Gjennomsnittshastigheten er sammenlignbar med raskere algoritmer som hurtigsort.
Steg-for-trinn-eksempel Rediger
Ta en rekke tall «5 1 4 2 8», og sorter matrisen fra laveste antall til største antall ved hjelp av boblesortering I hvert trinn sammenlignes elementer skrevet med fet skrift. Tre passeringer vil være påkrevd.
Første pasning (5 1 4 2 8) → (1 5 4 2 8). Her sammenligner algoritmen de to første elementene, og bytter siden 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Bytt siden 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Bytt siden 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Nå som disse elementene allerede er i orden (8 > 5), bytter ikke algoritme dem. Second Pass (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Bytt siden 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)
Nå er matrisen allerede sortert, men algoritmen vet ikke om den er fullført . Algoritmen trenger ett helt pass uten bytte for å vite at det er sortert.