Bubble Sort er en simpel algoritme, der bruges til at sortere et givet sæt n -elementer tilvejebragt i form af en matrix med n antal elementer. Boblesortering sammenligner alle elementerne en efter en og sorterer dem ud fra deres værdier.

Hvis det givne array skal sorteres i stigende rækkefølge, begynder boblesortering med at sammenligne det første element i arrayet med det andet element, hvis det første element er større end det andet element, bytter det begge elementerne og fortsætter derefter med at sammenligne det andet og det tredje element osv.

Hvis vi har total n -elementer, så er vi nødt til at gentage denne proces n-1 gange.

Det er kendt som boblesortering, fordi med hvert komplet iteration, det største element i det givne array, bobler op mod det sidste sted eller det højeste indeks, ligesom en vandboble stiger op til vandoverfladen.

Sortering finder sted ved at gå gennem alle elementerne en efter en og sammenligne det med det tilstødende element og bytte dem om nødvendigt.

BEMÆRK: Hvis du ikke er fortrolig med Sortering i datastruktur, skal du Lær først hvad der er sortering at vide om de grundlæggende i sortering.

Implementering af boblesorteringsalgoritme

Følgende er de trin, der er involveret i boblesortering (til sortering af en given matrix i stigende rækkefølge):

1. Start med det første element (index = 0), sammenlign det aktuelle element med det næste element i arrayet.
2. Hvis det aktuelle element er større end det næste element i arrayet, skift dem.
3. Hvis det aktuelle element er mindre end det næste element, skal du flytte til det næste element. Gentag trin 1.

Lad os se på en matrix med værdier {5, 1, 6, 2, 4, 3}

Nedenfor har vi en billedlig gengivelse af, hvordan boblesortering vil sortere det givne array.

Så som vi kan se i repræsentationen ovenfor, efter første iteration, 6 placeres ved det sidste indeks, hvilket er den rigtige position for det.

Tilsvarende efter den anden iteration, 5 vil være ved næstsidste indeks osv.

Tid til at skrive koden for boblesortering:

Selvom ovenstående logik vil sortere et usorteret array, er ovenstående algoritme stadig ikke effektiv, fordi den ydre for loop fortsætter med at udføre i 6 iterationer, selvom arrayet bliver sorteret efter den anden iteration.

Så vi kan tydeligt optimere vores algoritme.

Optimeret boblesorteringsalgoritme

For at optimere vores bobb le sort algoritme, vi kan introducere en flag for at overvåge, om elementer bliver byttet inde i den indre for loop.

Derfor kontrollerer vi i den indre for -sløjfe, om bytte af elementer finder sted eller ej, hver gang.

Hvis der ikke blev skiftet efter en bestemt iteration sted betyder det, at arrayet er sorteret, og vi kan hoppe ud af for -sløjfen i stedet for at udføre alle iterationerne.

Lad os se på et array med værdier {11, 17, 18, 26, 23}

Nedenfor har vi en billedlig gengivelse af, hvordan den optimerede boblesortering vil sortere det givne array.

Som vi kan se, skiftede vi i den første iteration, derfor opdaterede vi vores flag værdi til 1, som et resultat går udførelsen ind i for -sløjfen igen. Men i den anden iteration vil der ikke forekomme swapping, hvorfor værdien af flag forbliver 0, og eksekvering bryder ud af loop.

I ovenstående kode i funktionen bubbleSort, hvis det er en enkelt komplet cyklus af j iteration (indre for loop), ingen swapping finder sted, derefter flag forbliver 0 og så bryder vi ud af for sløjferne, fordi arrayet allerede er sorteret.

Kompleksitetsanalyse af boblesortering

I boblesortering foretages n-1 sammenligninger i 1. pasning, n-2 i 2. pas, n-3 i 3. pas og så videre. Så det samlede antal sammenligninger vil være,

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

Derfor er tidskompleksiteten af Bubblesortering O (n2).

Den største fordel ved Bubblesortering er algoritmens enkelhed.

Rumkompleksiteten for Bubblesortering er O (1), fordi der kun kræves et ekstra hukommelsesrum, dvs. for temp -variabel.

Også tidskompleksiteten i bedste tilfælde vil være O (n), det er når listen allerede er sorteret.

Følgende er tid og rum-kompleksitet for Bubble Sort-algoritmen.

Nu hvor vi har lært Bubble sorteringsalgoritme, kan du også tjekke disse sorteringsalgoritmer og deres applikationer:

• Indsætningssortering
• Valgssortering
• Hurtig sortering
• flet Sort
• Heap Sort
• Counting Sort