Bubble Sort regnes som en av de enkleste sorteringsalgoritmene som fungerer ved å bytte tilstøtende elementer gjentatte ganger hvis de er i feil rekkefølge. Med en boble sorteringsalgoritme vil du kunne se at det største elementet (forutsatt at vi sorterer fra minste til største) vil «boble» opp til toppen av listen eller matrisen.

Eksempel:
Anta at vi ønsker å sortere en liste eller en rekke elementer i stigende rekkefølge (fra minste til største): Liste = (3,1,2)

Siden ingen bytting skjedde, forteller dette oss at matrisen er allerede sortert i stigende rekkefølge!

Beste sak

La oss nå prøve den samme algoritmen igjen, men denne gangen ved å bruke best case-scenariet, som er når elementene allerede er sortert i rekkefølgen ( stigende) vil vi like.

Siden ingen bytte skjedde, er vi ferdige, og algoritmen gjorde bare to sammenligninger og antall elementer i matrisen vi vil kalle n = 3. Så vi kan se at for n elementer denne algoritmen vil i beste tilfelle bare ta n-1 sammenligninger, n-1 = O (n)

Prosedyren eller algoritmen vi brukte er nedenfor:

Denne algoritmen bruker et flagg for å fortelle om elementene er byttet ut eller ikke , som gjør at boble sorteringsalgoritmen i beste tilfelle kan være O (n) i stedet for O (n²) som en annen implementering av boble sortering.

Algoritmen ovenfor
Verste sak = O (n²)
Beste sak = O (n)

La oss se på en annen implementering av boblesorteringsalgoritmen:

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

Den ovennevnte algoritmen
Verste sak = O (n²)
Beste sak = O (n²)

Verste sak

La oss sortere en matrise eller liste = (3,2,1), dette vil være det verste tilfellet der listen er i helt motsatt rekkefølge enn den vi ønsker (i stigende rekkefølge) ved hjelp av algoritmen ovenfor.

First Pass:
(3,2,1) – > Sammenlign elementene 3 & 2
(2,3 , 1) – > Bytt 3 & 2 siden 2 < 3
( 2,3,1) – > Sammenlign elementene 3 & 1
(2,1,3) – > Bytt 1 & 3 siden 1 < 3

Second Pass:
(2,1,3) – > Sammenlign elementene 2 & 1
(1,2,3) – > Bytt 2 & 1 siden 1 < 2
(1,2,3) – > Sammenlign elementer 2 & 3
(1,2,3) – > Ingen bytte er nødvendig siden 2 < 3

Vi er nå ferdig med å sløyfe gjennom begge sløyfene, så matrisen må sorteres i stigende rekkefølge.

Legg merke til at vi gjorde 4 sammenligninger i det andre eksemplet ovenfor, og antall elementer i matrisen vi vil kalle ‘n’ = 3, så antall sammenligninger som er gjort er (n-1) ², og (n-1) ² = O (n²)

Også en flott bok for å forberede deg på koding / programmering intervjuer kalles cracking the coding interview. Det vil hjelpe deg å bli kjent med sorteringsalgoritmer og problemløsing, så husk å sjekke det ut!

Takk for at du leser denne artikkelen. Jeg håper det er nyttig for dere alle! Fortsett å lære, og hvis du vil ha flere videoer med algoritmeanalyse, kan du gå til og abonnere på YouTube-kanalene mine (randerson112358 & compsci112358)

Ta en titt på følgende for mer innhold / videoer om algoritmeanalyse og programmering:

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

compsci112358:

Nettsted:

Videotutorials om gjentakelsesrelasjon:

Video Tutorial on Algorithm Analysis:

Twitter: