Bubblesortering betragtes som en af de enkleste sorteringsalgoritmer, der fungerer ved gentagne gange at bytte de tilstødende elementer, hvis de er i den forkerte rækkefølge. Med en boble sorteringsalgoritme vil du kunne se, at det største element (forudsat at vi sorterer fra mindste til største) vil “boble” op til toppen af listen eller arrayet.

Eksempel:
Antag, at vi vil sortere en liste eller et array af elementer i stigende rækkefølge (fra mindste til største): Liste = (3,1,2)

Da der ikke skiftede noget, fortæller dette os, at arrayet er allerede sorteret i stigende rækkefølge!

Bedste tilfælde

Lad os nu prøve den samme algoritme igen, men denne gang ved hjælp af det bedste tilfælde, hvor elementerne allerede er sorteret i rækkefølgen ( stigende) vil vi gerne.

Da der ikke skete nogen bytte, er vi færdige, og algoritmen gjorde kun 2 sammenligninger og antallet af elementer i arrayet, vi kalder n = 3. Så vi kan se det for n elementer, denne algoritme tager i bedste fald kun n-1 sammenligninger, n-1 = O (n)

Proceduren eller algoritmen, som vi brugte, er nedenfor:

Denne algoritme bruger et flag for at fortælle om elementerne er byttet eller ej , som tillader, at boblesorteringsalgoritmen i bedste fald er O (n) i stedet for O (n²) som en anden implementering af boblesortering.

Ovenstående algoritme
Worst Case = O (n²)
Bedste sag = O (n)

Lad os se på en anden implementering af 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

Ovenstående algoritme
Værste sag = O (n²)
Bedste sag = O (n²)

Værste sag

Lad os sortere en matrix eller liste = (3,2,1) dette ville være det værste tilfælde, hvor listen er i den helt modsatte rækkefølge, end vi ønsker (i stigende rækkefølge) ved hjælp af ovenstående algoritme.

Første pas:
(3,2,1) – > Sammenlign elementerne 3 & 2
(2,3 , 1) – > Skift 3 & 2 siden 2 < 3
( 2,3,1) – > Sammenlign elementerne 3 & 1
(2,1,3) – > Skift 1 & 3 siden 1 < 3

Andet pass:
(2,1,3) – > Sammenlign elementerne 2 & 1
(1,2,3) – > Skift 2 & 1 siden 1 < 2
(1,2,3) – > Sammenlign elementer 2 & 3
(1,2,3) – > Ingen SWAPPING nødvendig siden 2 < 3

Vi er nu færdige med at løbe gennem begge sløjfer, så arrayet skal sorteres i stigende rækkefølge.

Bemærk, at vi foretog 4 sammenligninger i ovenstående andet eksempel, og antallet af elementer i arrayet vil vi kalde ‘n’ = 3, så antallet af sammenligninger er (n-1) ², og (n-1) ² = O (n²)

Også en god bog til at forberede dig til kodning / programmering af interviews kaldes cracking the coding interview. Det hjælper dig med at gøre dig bekendt med sorteringsalgoritmer og problemløsning, så sørg for at tjekke det ud!

Tak fordi du læste denne artikel. Jeg håber, det er nyttigt for jer alle! Fortsæt med at lære, og hvis du ønsker flere videoer med algoritmeanalyse, kan du besøge og abonnere på mine YouTube-kanaler (randerson112358 & compsci112358)

Tjek følgende for mere indhold / videoer om algoritmeanalyse og programmering:

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

compsci112358:

Websted:

Video-tutorials om gentagelsesrelation:

Video-tutorial om algoritmeanalyse:

Twitter: