Bubble Sort je jednoduchý triediaci algoritmus, ktorý opakovane prechádza zoznamom, porovnáva susediace prvky a zamieňa ich, ak sú v nesprávnom poradí. Nazýva sa 'Bubble Sort', pretože menšie prvky 'bublina' na začiatku zoznamu. Aj keď to nie je najefektívnejší algoritmus triedenia, je ľahké ho pochopiť a implementovať, vďaka čomu je dobrým východiskovým bodom pre učenie sa o algoritmoch triedenia. V tomto článku sa ponoríme do konceptu Bubble Sort, poskytneme implementáciu Pythonu s výstupom a rozoberieme časovú zložitosť algoritmu.

Pochopenie bublinového triedenia

Základnou myšlienkou Bubble Sort je opakovanie zoznamu, porovnávanie susedných prvkov a ich výmena, ak nie sú v poriadku. Proces pokračuje, kým nie sú potrebné žiadne ďalšie výmeny, čo znamená, že zoznam je teraz zoradený. Algoritmus dostal svoj názov podľa toho, ako sa menšie prvky postupne presúvajú na začiatok zoznamu, podobne ako bubliny stúpajúce na povrch.

Poďme si rozobrať kroky algoritmu Bubble Sort:

1. Iterácia cez zoznam: Začnite od začiatku zoznamu a porovnajte každý pár susediacich prvkov.
2. Porovnajte a vymeňte: Ak sú prvky v nesprávnom poradí, vymeňte ich. To zaisťuje, že väčší prvok „vybuchne“ a menší sa posunie nadol.
3. Pokračujte v iterácii: Opakujte postup pre každý pár susediacich prvkov, kým sa nedosiahne koniec zoznamu.
4. Opakujte do zoradenia: Pokračujte v iterácii cez zoznam, kým nie sú potrebné žiadne ďalšie výmeny. V tomto bode je zoznam zoradený.

Aj keď je bublinové triedenie jednoduché na pochopenie, nie je to najefektívnejší algoritmus triedenia, najmä pre veľké súbory údajov. Jeho časová zložitosť je v najhoršom prípade O(n^2), kde 'n' je počet prvkov v zozname. Táto kvadratická časová zložitosť ho robí menej vhodným pre veľké súbory údajov v porovnaní s pokročilejšími triediacimi algoritmami.

Implementácia Bubble Sort v Pythone

Teraz implementujme Bubble Sort v Pythone a pozorujme jeho správanie pomocou vzorového zoznamu:

 def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list) 

V tejto implementácii funkcia bubble_sort berie ako parameter zoznam (arr) a triedi ho na mieste. Vnorená slučka porovnáva susedné prvky a zamieňa ich, ak sú v nesprávnom poradí. Vonkajšia slučka zaisťuje, že sa proces opakuje, kým sa nezoradí celý zoznam.

Výstup a vysvetlenie

Spustite poskytnutý kód Pythonu so zoznamom vzoriek a sledujte výstup:

 Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90] 

Tu je pôvodný zoznam [64, 34, 25, 12, 22, 11, 90] úspešne zoradený pomocou algoritmu Bubble Sort, výsledkom čoho je zoradený zoznam [11, 12, 22, 25, 34, 64, 90].

Algoritmus opakovane prechádza zoznamom, porovnáva a vymieňa prvky, až kým nie je zoradený celý zoznam. V každom prechode najväčší netriedený prvok „prebubláva“ do svojej správnej polohy. Tento proces pokračuje, kým nie sú potrebné žiadne ďalšie výmeny, čo znamená, že zoznam je úplne zoradený.

Bublinkové triedenie úspešne triedi zoznam, je však dôležité poznamenať, že jeho časová zložitosť ho znižuje efektívnosť pre veľké množiny údajov v porovnaní s inými triediacimi algoritmami, ako sú Merge Sort alebo Quick Sort.

Časová zložitosť bublinkového triedenia

Pochopenie časovej zložitosti algoritmu je kľúčové pre hodnotenie jeho účinnosti, najmä pri práci s veľkými súbormi údajov. Časová zložitosť Bubble Sort je O(n^2) v najhoršom prípade, kde 'n' je počet prvkov v zozname.

Poďme si rozobrať analýzu časovej zložitosti:

• Vonkajšia slučka beží pre 'n' iterácií, kde 'n' je počet prvkov v zozname.
• Vnútorná slučka tiež beží pre 'n' iterácie v najhoršom prípade. Ako však algoritmus postupuje, počet iterácií vo vnútornej slučke klesá, pretože najväčší nezoradený prvok sa v každom prechode umiestni na svoju správnu pozíciu.
• V najhoršom prípade je počet porovnaní a zámien úmerný druhej mocnine počtu prvkov v zozname, čo vedie k časovej zložitosti O(n^2). Bubble Sort je preto pre veľké súbory údajov neefektívny a v aplikáciách v reálnom svete sa často uprednostňujú pokročilejšie algoritmy triedenia s lepšou časovou zložitosťou.

Záver

V tomto článku sme preskúmali koncepciu Bubble Sort, jednoduchého triediaceho algoritmu, ktorý opakovane porovnáva a zamieňa susediace prvky, kým nie je zoradený celý zoznam. Poskytli sme implementáciu Bubble Sort v Pythone, spustili sme ju so vzorovým zoznamom a analyzovali výstup. Okrem toho sme diskutovali o časovej zložitosti Bubble Sort, pričom sme zdôraznili jeho O(n^2) najhoršiu časovú zložitosť a jeho dôsledky na efektivitu.