Bubble Sort är en enkel algoritm som används för att sortera en given uppsättning n element tillhandahållna i form av en matris med n antal element. Bubble Sort jämför alla element en efter en och sorterar dem utifrån deras värden.

Om den givna matrisen måste sorteras i stigande ordning, börjar bubblasorteringen med att jämföra det första elementet i arrayen med det andra elementet, om det första elementet är större än det andra elementet, byter det båda elementen och fortsätter sedan för att jämföra det andra och det tredje elementet och så vidare.

Om vi har totalt n element, då måste vi upprepa denna process för n-1 gånger.

Det är känt som bubblasortering, för med varje komplett iteration bubblar det största elementet i den givna matrisen upp mot sista platsen eller det högsta indexet, precis som en vattenbubbla stiger upp till vattenytan.

Sortering sker genom att gå igenom elementen en efter en och jämföra den med intilliggande element och byta ut dem om det behövs.

OBS: Om du inte är bekant med Sortering i datastruktur bör du lär dig först vad som är att sortera för att veta om grunderna för sortering.

Implementering av bubblasorteringsalgoritm

Följande är stegen som är involverade i bubblasortering (för att sortera en given matris i stigande ordning):

1. Börja med det första elementet (index = 0), jämför det aktuella elementet med nästa element i matrisen.
2. Om det aktuella elementet är större än nästa element byt dem.
3. Om det aktuella elementet är mindre än nästa element, flytta till nästa element. Upprepa steg 1.

Låt oss betrakta en matris med värden {5, 1, 6, 2, 4, 3}

Nedan har vi en bildrepresentation av hur bubbelsortering kommer att sortera den givna matrisen.

Så som vi kan se i representationen ovan, efter första iteration, 6 placeras vid det sista indexet, vilket är rätt position för det.

På samma sätt efter den andra iterationen, 5 kommer att vara vid det näst sista indexet och så vidare.

Dags att skriva koden för bubblasortering:

Även om ovanstående logik kommer att sortera en osorterad matris, är ovanstående algoritm fortfarande inte effektiv eftersom den yttre for loop fortsätter att köras i 6 iterationer även om matrisen sorteras efter den andra iterationen.

Så vi kan tydligt optimera vår algoritm.

Optimerad bubbelsorteringsalgoritm

För att optimera vår bubbla le sort algoritm kan vi införa en flag för att övervaka om element byts in i den inre for slingan.

Därför kontrollerar vi i den inre for -slingan om byte av element äger rum eller inte, varje gång.

Om det inte tog någon byte för en viss iteration plats, det betyder att matrisen har sorterats och vi kan hoppa ut ur for -slingan istället för att utföra alla iterationer.

Låt oss betrakta en matris med värden {11, 17, 18, 26, 23}

Nedan har vi en bildrepresentation av hur den optimerade bubblasorteringen kommer att sortera den givna matrisen.

Som vi kan se, under den första iterationen ägde byte rum, därför uppdaterade vi vårt flag -värde till 1, som ett resultat kommer körningen in i for -slingan igen. Men i den andra iterationen kommer ingen byte att inträffa, därav kommer värdet av flag att förbli 0, och exekveringen kommer att brytas ur slingan.

I ovanstående kod, i funktionen bubbleSort, om för en enda fullständig cykel med j iteration (inre for loop), ingen byte sker, sedan flag förblir 0 och sedan bryter vi ut från for slingorna, eftersom arrayen redan har sorterats.

Komplexitetsanalys av bubbelsortering

I bubbelsortering kommer n-1 jämförelser att göras i första passet, n-2 i 2: a pass, n-3 i 3: e pass och så vidare. Så det totala antalet jämförelser blir,

(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2i.e O (n2)

Därför är tidskomplexiteten för Bubble Sort O (n2).

Den största fördelen med Bubble Sort är algoritmens enkelhet.

Utrymmeskomplexiteten för Bubblesortering är O (1), eftersom endast ett extra minnesutrymme krävs, dvs. för temp -variabel.

Dessutom är tidskomplexiteten i bästa fall O (n), det är när listan redan är sorterad.

Följande är tid och rymdkomplexitet för Bubble Sort-algoritmen.

Nu när vi har lärt oss Bubblesorteringsalgoritmen kan du också kolla in dessa sorteringsalgoritmer och deras applikationer:

• Insättningssortering
• Urvalssortering
• Snabbsortering
• slå samman Sortera
• Heapsortering
• Räkna sortering