Bubble Sort je jednoduchý třídicí algoritmus, který opakovaně prochází seznamem, porovnává sousední prvky a zaměňuje je, pokud jsou ve špatném pořadí. Jmenuje se 'Bubble Sort', protože menší prvky 'bublinou' na začátek seznamu. Ačkoli to není nejúčinnější třídicí algoritmus, je snadné jej pochopit a implementovat, což z něj činí dobrý výchozí bod pro učení se o algoritmech třídění. V tomto článku se ponoříme do konceptu Bubble Sort, poskytneme implementaci Pythonu s výstupem a probereme časovou složitost algoritmu.
Porozumění bublinovému třídění
Základní myšlenkou Bubble Sort je procházet seznam vícekrát, porovnávat sousední prvky a zaměňovat je, pokud nejsou v pořádku. Proces pokračuje, dokud nejsou potřeba žádné další swapy, což znamená, že seznam je nyní seřazen. Algoritmus dostal svůj název podle toho, jak se menší prvky postupně přesouvají na začátek seznamu, podobně jako bubliny stoupající na povrch.
Pojďme si rozebrat kroky algoritmu Bubble Sort:
arraylist v java sort
- Iterace seznamu: Začněte od začátku seznamu a porovnejte každý pár sousedních prvků.
- Porovnejte a vyměňte: Pokud jsou prvky ve špatném pořadí, vyměňte je. Tím je zajištěno, že větší prvek „bublá“ a menší se pohybuje dolů.
- Pokračujte v iteraci: Opakujte proces pro každou dvojici sousedních prvků, dokud nedosáhnete konce seznamu.
- Opakujte, dokud nebude seřazeno: Pokračujte v iteraci seznamu, dokud již nebudou potřeba žádné výměny. V tomto okamžiku je seznam seřazen.
I když je bublinkové třídění jednoduché na pochopení, není to nejúčinnější třídicí algoritmus, zejména pro velké soubory dat. Jeho časová složitost je v nejhorším případě O(n^2), kde 'n' je počet prvků v seznamu. Tato kvadratická časová složitost jej činí méně vhodným pro velké soubory dat ve srovnání s pokročilejšími třídicími algoritmy.
Implementace bublinového třídění v Pythonu
Nyní implementujme Bubble Sort v Pythonu a pozorujme jeho chování pomocí ukázkového seznamu:
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 této implementaci bere funkce bubble_sort jako svůj parametr seznam (arr) a třídí jej na místě. Vnořená smyčka porovnává sousední prvky a zaměňuje je, pokud jsou ve špatném pořadí. Vnější smyčka zajišťuje opakování procesu, dokud není celý seznam setříděn.
Výstup a vysvětlení
Spusťte poskytnutý kód Pythonu s ukázkovým seznamem a sledujte výstup:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
Zde je původní seznam [64, 34, 25, 12, 22, 11, 90] úspěšně setříděn pomocí algoritmu Bubble Sort, výsledkem je seřazený seznam [11, 12, 22, 25, 34, 64, 90].
np tečka
Algoritmus prochází seznamem několikrát, porovnává a vyměňuje prvky, dokud není celý seznam seřazen. V každém průchodu největší netříděný prvek „vybuchne“ do své správné polohy. Tento proces pokračuje, dokud nejsou potřeba žádné další swapy, což znamená, že seznam je plně seřazen.
Bublinové třídění sice seznam úspěšně třídí, je však důležité poznamenat, že jeho časová složitost snižuje efektivitu pro velké datové sady ve srovnání s jinými třídicími algoritmy, jako je Merge Sort nebo Rychlé třídění.
Časová složitost bublinového řazení
vyměnit vše
Pochopení časové složitosti algoritmu je klíčové pro hodnocení jeho účinnosti, zejména při práci s velkými datovými soubory. Časová složitost Bubble Sort je v nejhorším případě O(n^2), kde 'n' je počet prvků v seznamu.
Pojďme si rozebrat analýzu časové složitosti:
- Vnější smyčka běží po 'n' iteracích, kde 'n' je počet prvků v seznamu.
- Vnitřní smyčka také běží pro 'n' iterace v nejhorším případě. Jak však algoritmus postupuje, počet iterací ve vnitřní smyčce klesá, protože největší neseřazený prvek se v každém průchodu umístí na svou správnou pozici.
- V nejhorším případě je počet porovnání a záměn úměrný druhé mocnině počtu prvků v seznamu, což má za následek časovou složitost O(n^2). Díky tomu je Bubble Sort pro velké datové sady neefektivní a v aplikacích v reálném světě jsou často preferovány pokročilejší třídicí algoritmy s lepší časovou složitostí.
Závěr
V tomto článku jsme prozkoumali koncept Bubble Sort, jednoduchý třídicí algoritmus, který opakovaně porovnává a zaměňuje sousední prvky, dokud není seřazen celý seznam. Poskytli jsme implementaci Bubble Sort v Pythonu, spustili jsme ji s ukázkovým seznamem a analyzovali výstup. Kromě toho jsme diskutovali o časové složitosti Bubble Sort a zdůraznili jsme jeho O(n^2) nejhorší časovou složitost a jeho důsledky pro efektivitu.