Bubblesortering

PerformanceEdit

Bubblesortering har en värsta fall och genomsnittlig komplexitet av О (n2), där n är antalet objekt som sorteras. De flesta praktiska sorteringsalgoritmer har betydligt bättre värsta eller genomsnittliga komplexitet, ofta O (n log n). Även andra О (n2) sorteringsalgoritmer, som insättningssortering, går i allmänhet snabbare än bubblasortering och är inte mer komplexa. Därför är bubblasortering inte en praktisk sorteringsalgoritm.

Den enda betydande fördelen som bubblasortering har jämfört med de flesta andra algoritmer, till och med snabbsortering, men inte insättningssortering, är att förmågan att upptäcka att listan är sorterad är effektivt inbyggt i algoritmen. När listan redan är sorterad (bästa fall) är bubblasorteringens komplexitet bara O (n). Däremot utför de flesta andra algoritmer, även de med bättre genomsnittlig komplexitet, hela sin sorteringsprocess på uppsättningen och är därmed mer komplexa. Emellertid delar inte bara införingssorteringen den här fördelen, men den fungerar också bättre på en lista som är väsentligen sorterad (med ett litet antal inversioner). Om detta beteende önskas kan det dessutom läggas till trivialt till någon annan algoritm genom att kontrollera listan innan algoritmen körs.

Bubbelsortering bör undvikas vid stora samlingar. Det är inte effektivt i fallet med en omvänd ordnad samling.

Rabbits and TurtlesEdit

Avståndet och riktningen som elementen måste röra sig under sorten bestämmer bubblans sorterings prestanda eftersom element rör sig i olika riktningar med olika hastigheter. Ett element som måste röra sig mot slutet av listan kan röra sig snabbt eftersom det kan delta i successiva byten. Till exempel kommer det största elementet i listan att vinna varje byte, så det flyttar till dess sorterade position vid första passet även om det börjar nära början. Å andra sidan kan ett element som måste röra sig mot början av listan inte röra sig snabbare än ett steg per pass, så element rör sig mycket långsamt mot början. det minsta elementet är i slutet av listan, det tar n − 1 pass för att flytta det till början. Detta har lett till att dessa typer av element har fått namnet kaniner respektive sköldpaddor efter karaktärerna i Aesops fabel av Sköldpaddan och haren.

Olika ansträngningar har gjorts för att eliminera sköldpaddor för att förbättra bubblans sorteringshastighet. Cocktailsortering är en dubbelriktad bubbelsortering som går från början till slut och sedan vänder sig och går från början till början. Det kan flytta sköldpaddor ganska bra, men det behåller O (n2) värsta fallets komplexitet. Kombsortering jämför element åtskilda av stora luckor och kan flytta sköldpaddor extremt snabbt innan du fortsätter till mindre och mindre luckor för att jämna ut listan. Dess genomsnittliga hastighet kan jämföras med snabbare algoritmer som quicksort.

Steg-för-steg-exempelRedigera

Ta en rad siffror ”5 1 4 2 8” och sortera matrisen från det lägsta nummer till största antal med hjälp av bubblasortering. I varje steg jämförs element skrivna med fet stil. Tre pass kommer att krävas;

First Pass (5 1 4 2 8) → (1 5 4 2 8), Här jämför algoritmen de två första elementen och byter sedan 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Byt sedan 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Byt sedan 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Nu eftersom dessa element redan är i ordning (8 > 5), växlar algoritmen inte dem. Andra passet (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Byt sedan 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

Nu är arrayen redan sorterad, men algoritmen vet inte om den är klar . Algoritmen behöver ett helt pass utan någon byte för att veta att den är sorterad.