Bubblesortering anses vara en av de enklaste sorteringsalgoritmerna som fungerar genom att upprepade gånger byta intilliggande element om de är i fel ordning. Med en algoritm för bubblasortering kommer du att kunna se att det största elementet (förutsatt att vi sorterar från minsta till största) kommer att ”bubbla” upp till toppen av listan eller matrisen.

Exempel:
Antag att vi vill sortera en lista eller matris med element i stigande ordning (från minsta till största): List = (3,1,2)

Eftersom ingen byte inträffade berättar detta att matrisen är redan sorterad i stigande ordning!

Bästa fallet

Låt oss nu prova samma algoritm igen men den här gången använder vi bästa fallsscenariot, det är när elementen redan är sorterade i ordningen ( stigande) skulle vi vilja.

Eftersom ingen byte inträffade är vi klara och algoritmen gjorde bara två jämförelser och antalet element i matrisen som vi kommer att kalla n = 3. Så vi kan se att för n element i detta fall tar algoritmerna i bästa fall endast n-1-jämförelser, n-1 = O (n)

Proceduren eller algoritmen som vi använde är nedan:

Denna algoritm använder en flagga för att berätta om elementen har bytts ut eller inte , vilket gör att bubblasorteringsalgoritmen i bästa fall kan vara O (n) istället för O (n²) som en annan implementering av bubblasortering.

Ovanstående algoritm
Worst Case = O (n²)
Bästa fall = O (n)

Låt oss ta en titt på en annan implementering av bubblasorteringsalgoritmen:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

Ovanstående algoritm – Värsta fall = O (n²)
Bästa fall = O (n²)

Värsta fall

Låt oss sortera en matris eller lista = (3,2,1) det här skulle vara det värsta fallet där listan är i helt motsatt ordning än vad vi önskar (i stigande ordning) med ovanstående algoritm.

First Pass:
(3,2,1) – > Jämför elementen 3 & 2
(2,3 , 1) – > Byt 3 & 2 sedan 2 < 3
( 2,3,1) – > Jämför elementen 3 & 1
(2,1,3) – > Byt 1 & 3 sedan 1 < 3

Andra pass:
(2,1,3) – > Jämför elementen 2 & 1
(1,2,3) – > Byt 2 & 1 sedan 1 < 2
(1,2,3) – > Jämför element 2 & 3
(1,2,3) – > Ingen byte behövs sedan 2 < 3

Vi har nu slutat slinga igenom båda slingorna så att matrisen måste sorteras i stigande ordning.

Observera att vi gjorde 4 jämförelser i ovanstående andra exempel, och antalet element i matrisen kommer vi att kalla ’n’ = 3, så antalet jämförelser som gjorts är (n-1) ², och (n-1) ² = O (n²)

En bra bok som förbereder dig för kodnings- / programmeringsintervjuer kallas också för att knäcka kodningsintervjun. Det hjälper dig att bekanta dig med sorteringsalgoritmer och problemlösning, så se till att kolla in det!

Tack för att du läser den här artikeln. Jag hoppas att det är till hjälp för er alla! Fortsätt lära dig, och om du vill ha fler videor med algoritmanalys, vänligen besök och prenumerera på mina YouTube-kanaler (randerson112358 & compsci112358)

Kolla in följande för mer innehåll / videor om algoritmanalys och programmering:

YouTube-kanal:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Webbplats:

Videohandledning om återkommande relation:

Videohandledning om algoritmanalys:

Twitter: