Bubble sort

PerformanceEdit

Bubble sort heeft een worst-case en gemiddelde complexiteit van О (n2), waarbij n het aantal items is dat wordt gesorteerd. De meeste praktische sorteeralgoritmen hebben een aanzienlijk betere worst-case of gemiddelde complexiteit, vaak O (n log n). Zelfs andere О (n2) sorteeralgoritmen, zoals invoegsortering, werken over het algemeen sneller dan bellen sorteren en zijn niet complexer. Daarom is bellen sorteren geen praktisch sorteeralgoritme.

Het enige significante voordeel dat bellen sorteren heeft ten opzichte van de meeste andere algoritmen, zelfs quicksort, maar niet invoegsortering, is dat de mogelijkheid om te detecteren dat de lijst is gesorteerd efficiënt is ingebouwd in het algoritme. Als de lijst al is gesorteerd (in het beste geval), is de complexiteit van het sorteren van bellen alleen O (n). Daarentegen voeren de meeste andere algoritmen, zelfs die met een betere gemiddelde complexiteit, hun hele sorteerproces uit op de set en zijn ze dus complexer. Invoegsortering deelt dit voordeel echter niet alleen, maar presteert ook beter op een lijst die substantieel is gesorteerd (met een klein aantal inversies). Als dit gedrag gewenst is, kan het bovendien triviaal worden toegevoegd aan elk ander algoritme door de lijst te controleren voordat het algoritme wordt uitgevoerd.

Het sorteren van bellen moet worden vermeden in het geval van grote verzamelingen. Het zal niet efficiënt zijn in het geval van een verzameling in omgekeerde volgorde.

Konijnen en schildpadden Bewerken

De afstand en richting die elementen moeten bewegen tijdens het sorteren bepalen de prestatie van de bellensortering, omdat elementen bewegen in verschillende richtingen met verschillende snelheden. Een element dat naar het einde van de lijst moet bewegen, kan snel bewegen omdat het kan deelnemen aan opeenvolgende swaps. Het grootste element in de lijst wint bijvoorbeeld elke ruil, dus het gaat naar de gesorteerde positie op de eerste doorgang, zelfs als het bij het begin begint. Aan de andere kant kan een element dat naar het begin van de lijst moet bewegen, niet sneller dan één stap per doorgang bewegen, dus elementen gaan heel langzaam naar het begin. het kleinste element aan het einde van de lijst staat, er zijn n − 1 passen nodig om het naar het begin te verplaatsen. Dit heeft ertoe geleid dat dit soort elementen respectievelijk konijnen en schildpadden worden genoemd, naar de karakters in Aesops fabel van De schildpad en de haas.

Diverse er zijn pogingen gedaan om schildpadden te elimineren om de snelheid van het bellen te verbeteren. Cocktailsoort is een bidirectionele bubbelsoort die van begin tot eind gaat, en dan zichzelf omkeert, van begin tot begin. Het kan schildpadden redelijk goed verplaatsen, maar het behoudt de O (n2) worst-case complexiteit. Comb sort vergelijkt elementen die worden gescheiden door grote openingen, en kan schildpadden extreem snel verplaatsen voordat ze doorgaan naar kleinere en kleinere openingen om de lijst glad te strijken. De gemiddelde snelheid is vergelijkbaar met snellere algoritmen zoals quicksort.

Stapsgewijs voorbeeld Bewerken

Neem een reeks getallen “5 1 4 2 8” en sorteer de reeks van de laagste nummer tot grootste nummer met behulp van bellen sorteren. Bij elke stap worden vetgedrukte elementen vergeleken. Er zijn drie slagen vereist;

Eerste doorgang (5 1 4 2 8) → (1 5 4 2 8), hier vergelijkt het algoritme de eerste twee elementen en wisselt ze sinds 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), wisselen sinds 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Wissel sinds 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Nu, aangezien deze elementen al in orde zijn (8 > 5), wisselt het algoritme ze niet om. Tweede doorgang (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Wisselen sinds 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

Nu is de array al gesorteerd, maar het algoritme weet niet of deze is voltooid . Het algoritme heeft één hele doorgang nodig zonder enige ruil om te weten dat het gesorteerd is.