Třídění podle jednoduchých výměn , třídění podle bubliny ( anglicky bubble sort ) je jednoduchý třídicí algoritmus . Pochopení a implementace tohoto algoritmu je nejjednodušší, ale je efektivní pouze pro malá pole. Složitost algoritmu: .
Algoritmus je považován za výukový a mimo výukovou literaturu se prakticky nepoužívá, místo toho se v praxi používají efektivnější třídicí algoritmy. Metoda výměnného třídění je zároveň základem některých pokročilejších algoritmů, jako je shaker sort , heap sort a quick sort .
Algoritmus se skládá z opakovaných průchodů tříděným polem. Pro každý průchod jsou prvky postupně porovnávány ve dvojicích, a pokud je pořadí v páru nesprávné, prvky jsou permutovány. Průchody polem se opakují jednou nebo dokud se při dalším průchodu neukáže, že výměny již nejsou potřeba, což znamená, že pole je vytříděno. S každým průchodem algoritmu vnitřní smyčkou se další největší prvek pole umístí na své místo na konec pole vedle předchozího „největšího prvku“ a nejmenší prvek se posune o jednu pozici na začátek pole. pole („plave“ do požadované polohy, jako bublina ve vodě – odtud i název algoritmu).
Obtížnost: .
Nejhorší případ:
Nejlepší případ (zadáno již seřazené pole):
Zvláštnost tohoto algoritmu je následující: po prvním dokončení vnitřní smyčky je maximální prvek pole vždy na -té pozici. Při druhém průchodu je na místě další největší prvek. A tak dále. Při každém dalším průchodu se tedy počet zpracovávaných prvků sníží o 1 a není potřeba pokaždé „projíždět“ celé pole od začátku do konce.
Vzhledem k tomu, že podpole jednoho prvku není nutné třídit, řazení nevyžaduje více než iterace vnější smyčky. V některých implementacích proto vnější smyčka vždy běží hladce a nesleduje, zda při každé iteraci byly nebo nebyly žádné výměny.
Zavedení indikátoru (příznak F) skutečných výměn ve vnitřní smyčce snižuje počet průchodů navíc v případech s částečně tříděnými vstupními poli. Před každým průchodem vnitřní smyčkou je příznak resetován na 0 a poté, co k výměně skutečně došlo, je nastaven na 1. Pokud je příznak po opuštění vnitřní smyčky 0, pak nedošlo k žádným výměnám, tedy pole je seřazeno a program třídění můžete ukončit s předstihem.
Pseudokód pro ještě vylepšený algoritmus s kontrolou skutečně nastalých výměn ve vnitřní smyčce.
Vstup: pole sestávající z prvků, číslovaných od do
SMYČKA PRO J = 1 AŽ N - 1 KROK 1 PRO J = 1 AŽ N - 1 KROK 1 F = 0 F = 0 SMYČKA PRO I = 0 AŽ N - 1 - J KROK 1 PRO I = 0 AŽ N - 1 - J KROK 1 POKUD A [ I ] > A [ I + 1 ] PAK VYMĚŇTE A [ I ], A [ I + 1 ]: F = 1 POKUD A [ I ] > A [ I + 1 ] PAK VYMĚŇTE A [ I ], A [ I + 1 ]: F = 1 DALŠÍ I DALŠÍ I POKUD F = 0 POTOM UKONČIT SMYČKU , POKUD F = 0 , POTOM ODEJÍT NA DALŠÍ J DALŠÍ JV případě předčasného ukončení třídění tento algoritmus provede jeden redundantní průchod bez výměn.
Nejhorší případ (nezlepší se):
Nejlepší případ (vylepšeno):
Doba třídění 10 000 krátkých celých čísel na stejném hardwarově-softwarovém komplexu (porovnávací operace ≈3,4 µs, výměna ≈2,3 µs) podle selekčního řazení byla ≈40 s, u ještě vylepšeného bublinkového třídění ≈30 s a u rychlého řazení ≈ 0,027 sek.
větší než merge sort , ale v malém rozdíl není příliš velký a programový kód je velmi jednoduchý, takže je docela přijatelné používat bublinové třídění pro mnoho úloh s nízkorozměrnými poli na nečinných a málo zatížených strojích.
Algoritmus lze mírně vylepšit provedením následujícího:
V bublinovém třídění můžete při každém průchodu vnitřní smyčkou přidat definici dalšího minimálního prvku a umístit jej na začátek pole, to znamená kombinovat algoritmy třídění podle bublin a výběru , přičemž počet průchodů vnitřní smyčka je poloviční, ale po každém průchodu vnitřní smyčkou se přidává počet srovnání a jedna výměna.
Pseudokód kombinovaného algoritmu třídění bublin a výběru ( stabilní implementace):
PRO J = 0 DO N - 1 KROK 1 F = 0 MIN = J PRO I = J DO N - 1 - J KROK 1 POKUD Y [ I ] > Y [ I + 1 ] PAK VYMĚŇTE Y [ I ], Y [ I + 1 ]: F = 1 POKUD Y [ I ] < Y [ MIN ] POTOM MIN = I DALŠÍ I POKUD F = 0 POTOM ODCHOD PRO POKUD MIN <> J POTOM VYMĚŇTE Y [ J ], Y [ MIN ] DALŠÍ JVezměme pole s čísly "5 1 4 2 8" a seřaďme hodnoty vzestupně pomocí bublinového řazení. Ty prvky, které jsou v této fázi porovnávány, jsou zvýrazněny.
První průchod:
( 5 1 4 2 8) ( 1 5 4 2 8), Zde algoritmus porovnává první dva prvky a prohodí je. (1 5 4 2 8) (1 4 5 2 8), Vymění, protože (1 4 5 2 8) (1 4 2 5 8), Vymění, protože (1 4 2 5 8 ) (1 4 2 5 8 ), Protože jsou prvky na svých místech ( ), algoritmus je nezamění.Druhý průchod:
( 1 4 2 5 8) ( 1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), Vymění, protože (1 2 4 5 8) (1 2 4 5 8)Nyní je pole kompletně seřazeno, ale algoritmus to neví. Proto potřebuje provést úplný průchod a určit, že neexistovaly žádné permutace prvků.
Třetí průchod:
( 1 2 4 5 8) ( 1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)Nyní je pole seřazeno a algoritmus může být dokončen.
![]() |
---|
Algoritmy řazení | |
---|---|
Teorie | Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí |
Výměna | |
Výběr | |
vložky | |
fúze | |
Žádné srovnání | |
hybridní | |
jiný | |
nepraktický |