Boblesortering

PerformanceEdit

Boblesortering har en worst-case og gennemsnitlig kompleksitet på О (n2), hvor n er antallet af varer, der sorteres. De fleste praktiske sorteringsalgoritmer har væsentligt bedre worst-case eller gennemsnitlig kompleksitet, ofte O (n log n). Selv andre О (n2) sorteringsalgoritmer, som f.eks. Indsætningssortering, kører generelt hurtigere end boblesortering og er ikke mere komplekse. Derfor er boblesortering ikke en praktisk sorteringsalgoritme.

Den eneste betydelige fordel, som boblesortering har i forhold til de fleste andre algoritmer, endda quicksort, men ikke indsættelsessortering, er, at evnen til at opdage, at listen er sorteret er effektivt indbygget i algoritmen. Når listen allerede er sorteret (best-case), er kompleksiteten af boblesortering kun O (n). Derimod udfører de fleste andre algoritmer, selv dem med bedre gennemsnitssagskompleksitet, hele deres sorteringsproces på sættet og er således mere komplekse. Imidlertid deler ikke indsættelsessorteringen denne fordel, men den fungerer også bedre på en liste, der er væsentligt sorteret (med et lille antal inversioner). Hvis denne adfærd ønskes, kan den derudover tilføjes trivielt til enhver anden algoritme ved at kontrollere listen, før algoritmen kører.

Boblesortering bør undgås i tilfælde af store samlinger. Det er ikke effektivt i tilfælde af en omvendt ordnet samling.

Rabbits and TurtlesEdit

Den afstand og retning, som elementerne skal bevæge sig under sorteringen, bestemmer boblesorterings ydeevne, fordi elementer bevæger sig i forskellige retninger med forskellige hastigheder. Et element, der skal bevæge sig mod slutningen af listen, kan bevæge sig hurtigt, fordi det kan deltage i successive swaps. F.eks. vinder det største element på listen hver swap, så det flytter til dens sorterede position ved det første pass, selvom det starter nær begyndelsen. På den anden side kan et element, der skal bevæge sig mod begyndelsen af listen, ikke bevæge sig hurtigere end et trin pr. pas, så elementerne bevæger sig meget langsomt mod starten. det mindste element er i slutningen af listen, det tager n − 1 pass for at flytte det til begyndelsen. Dette har ført til, at disse typer af elementer er navngivet henholdsvis kaniner og skildpadder, efter tegnene i Æsops fabel af Skildpadden og haren.

Forskellige der er gjort en indsats for at eliminere skildpadder for at forbedre hastigheden af sorteringen af bobler. Cocktailsortering er en tovejs boblesortering, der går fra start til slut, og derefter vender sig selv, går ende til start. Det kan flytte skildpadder ret godt, men det bevarer O (n2) worst-case kompleksitet. Kamsortering sammenligner elementer adskilt af store huller og kan flytte skildpadder ekstremt hurtigt, inden du fortsætter til mindre og mindre huller for at udjævne listen. Dens gennemsnitshastighed kan sammenlignes med hurtigere algoritmer som quicksort.

Trin-for-trin-eksempel Rediger

Tag en matrix med tal “5 1 4 2 8”, og sorter arrayet fra det laveste nummer til største antal ved hjælp af boblesortering. I hvert trin sammenlignes elementer skrevet med fed skrift. Tre gennemløb kræves;

Første pas (5 1 4 2 8) → (1 5 4 2 8), Her sammenligner algoritme de to første elementer og bytter siden 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Byt siden 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Byt siden 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Nu da disse elementer allerede er i rækkefølge (8 > 5), bytter algoritme dem ikke. Andet pass (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Byt siden 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

Nu er arrayet allerede sorteret, men algoritmen ved ikke, om det er afsluttet . Algoritmen har brug for et helt pas uden swap for at vide, at det er sorteret.