Bublinový druh

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: . $Ó$ $(n^{2})$

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

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). $N-1$

Implementace

Obtížnost: . $O(n^{2})$

Nejhorší případ:

Počet porovnání v těle smyčky je . $(N-1){\frac N2}$
Počet porovnání v záhlaví smyček je . $(N-1){\frac N2}$
Celkový počet srovnání je . $(N-1)N$
Počet přiřazení v záhlaví smyček je . $(N-1){\frac N2}$
Počet výměn je roven , což je krát více než při třídění výběru . $(N-1){\frac N2}$ ${\frac N2}$

Nejlepší případ (zadáno již seřazené pole):

Počet porovnání v těle smyčky je . $(N-1){\frac N2}$
Počet porovnání v záhlaví smyček je . $(N-1){\frac N2}$
Celkový počet srovnání je . $(N-1)N$
Počet výměn je . $0$

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. $N$ $N-1$

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. $N-1$ $N-1$

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 $A[N]$ $N$ $A[0]$ $A[N-1]$

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ŠÍ J

V 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):

Počet porovnání v těle smyčky je . $(N-1){\frac N2}$
Počet porovnání v záhlaví smyček . $(N-1){\frac N2}$
Celkový počet srovnání je . $(N-1)N$
Počet přiřazení v záhlaví smyček je . $(N-1){\frac N2}$
Počet výměn je . $(N-1){\frac N2}$

Nejlepší případ (vylepšeno):

Počet porovnání v těle smyčky je . $(N-1)$
Počet porovnání v záhlaví smyček . $(N-1)$
Celkový počet srovnání je . $2 (N-1)$
Počet výměn je . $0$

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.

$O(n\cdot n)$ 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. $O(n\cdot\log n)$ $n$

Algoritmus lze mírně vylepšit provedením následujícího:

Vnitřní smyčku lze upravit tak, aby střídavě skenovala pole od začátku a poté od konce. Takto upravený algoritmus se nazývá shuffle sort nebo shaker sort. To nesnižuje složitost . $O(n\cdot n)$

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ŠÍ J

Příklad toho, jak algoritmus funguje

Vezmě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

5>4

(1 4 5 2 8) (1 4 2 5 8), Vymění, protože

5>2

(1 4 2 5 8 ) (1 4 2 5 8 ), Protože jsou prvky na svých místech ( ), algoritmus je nezamění.

8>5

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

4>2

(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.

Odkazy

Animace třídicích algoritmů
Dynamická vizualizace 7 Open Source třídicí algoritmy
Levitin A. V. Kapitola 3. Metoda hrubé síly: Bubble sort // Algorithms. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 144-146. — 576 s. — ISBN 978-5-8459-0987-9

Slovníky a encyklopedie	velká čínština

Algoritmy řazení
Teorie	Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna	bublina Míchání Trpaslíci Rychle Hřeben Řazení sudé-liché bitový
Výběr	Výběr Pyramidový Hladký
vložky	vložky shella strom
fúze	fúze
Žádné srovnání	Počítací blok
hybridní	introsort Timsort
jiný	Topologické sítí biton
nepraktický	Bogosort Stooge řazení lívanec pomalý