Čo je to algoritmus bublinového triedenia [Vysvetlené na príkladoch]

Bublinové triedenie je jedným z najjednoduchších triediacich algoritmov, ktorý iteruje dané pole a porovnáva susediace prvky. Ak sú prvky v nesprávnom poradí, vymenia sa, aby boli v správnom poradí. Tento proces pokračuje, kým nie je zoradené celé pole.

Algoritmus:

Krok 1:Opakujte pole viackrát

V každej iterácii porovnajte susedné prvky (i a i + 1)

Krok 2:Ak je aktuálny prvok (i) väčší ako nasledujúci prvok (i + 1), vymeňte ich

Opakujte tento postup, kým nie je zoradené celé pole

Časová zložitosť:

O(n^2), pretože prechádza cez pole viackrát a v každej iterácii vykonáva porovnania a swapy.

Príklad kódu v Pythone:

def bubble_sort(arr):

pre i v rozsahu (len(arr) - 1):

# Iterujte cez pole a porovnajte susedné prvky

pre j v rozsahu(len(arr) - 1 - i):

# Porovnajte aktuálny prvok s nasledujúcim prvkom

ak arr[j]> arr[j + 1]:

# Vymeňte prvky, ak sú v nesprávnom poradí

arr[j], arr[j + 1] =arr[j + 1], arr[j]

# Vráti zoradené pole

vrátiť arr

Príklad:

Vstup:

[5, 3, 1, 2, 4]

výstup:

[1, 2, 3, 4, 5]

Algoritmus bublinového triedenia iteruje cez pole a porovnáva susediace prvky. Ak sú v nesprávnom poradí, vymenia sa. Tento proces sa opakuje, kým nie je zoradené celé pole.

Takto funguje algoritmus v tomto príklade:

Iterácia 1:

- Porovnajte 5 a 3:Vymeňte ich, pretože 5 je väčšie ako 3.

- Porovnajte 3 a 1:Vymeňte ich, pretože 3 je väčšie ako 1.

- Porovnanie 2 a 4:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Pole sa zmení na:[3, 1, 2, 4, 5].

Iterácia 2:

- Porovnajte 3 a 1:Vymeňte ich, pretože 3 je väčšie ako 1.

- Porovnanie 1 a 2:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Porovnanie 2 a 4:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Pole sa zmení na:[1, 2, 3, 4, 5].

Iterácia 3:

- Porovnanie 1 a 2:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Porovnanie 2 a 3:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Porovnanie 3 a 4:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Pole sa zmení na:[1, 2, 3, 4, 5].

Iterácia 4:

- Porovnanie 1 a 2:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Porovnanie 2 a 3:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Porovnanie 3 a 4:Nie je potrebná žiadna výmena, pretože sú v správnom poradí.

- Pole zostáva nezmenené.

Po štvrtej iterácii sa pole zoradí vo vzostupnom poradí:[1, 2, 3, 4, 5].

• Predchádzajúca strana: Čo je algoritmus rýchleho triedenia [Vysvetlené na príkladoch] 
• Ďalšia strana: Čo je algoritmus triedenia výberu [vysvetlené na praktickom príklade]