Bublinkové třídění - Bubble sort

Bublinkové řazení

Statická vizualizace bublinového řazení
Třída	Algoritmus řazení
Datová struktura	Pole
Nejhorší výkon	${\ displaystyle O (n^{2})}$srovnání, swapy${\ displaystyle O (n^{2})}$
Nejlepší výkon	${\ Displaystyle O (n)}$srovnání, swapy${\ displaystyle O (1)}$
Průměrný výkon	${\ displaystyle O (n^{2})}$srovnání, swapy${\ displaystyle O (n^{2})}$
Nejhorší prostorová složitost	${\ Displaystyle O (n)}$celkem, pomocný${\ displaystyle O (1)}$

Řazení bublin , někdy označované jako potápějící se řazení , je jednoduchý algoritmus řazení, který opakovaně prochází seznamem, porovnává sousední prvky a zaměňuje je, pokud jsou ve špatném pořadí. Průchod seznamem se opakuje, dokud není seznam seřazen. Algoritmus, který je srovnávacím druhem , je pojmenován podle toho, jak menší nebo větší prvky „bublinují“ na začátek seznamu.

Tento jednoduchý algoritmus funguje v reálném světě špatně a používá se především jako vzdělávací nástroj. Efektivnější algoritmy, jako je quicksort , timsort nebo merge sort, používají třídicí knihovny zabudované do populárních programovacích jazyků, jako je Python a Java.

Analýza

Příklad bublinového řazení. Začněte od začátku seznamu a porovnejte všechny sousední páry a vyměňte jejich polohu, pokud nejsou ve správném pořadí (ten druhý je menší než ten předchozí). Po každé iteraci je třeba porovnat o jeden prvek méně (poslední), dokud nezbývají žádné další prvky ke srovnání.

Výkon

Bublinkové třídění má nejhorší případ a průměrnou složitost О ( n ² ), kde n je počet tříděných položek. Většina praktických třídicích algoritmů má podstatně lepší nejhorší nebo průměrnou složitost, často O ( n  log  n ). Dokonce i jiné algoritmy řazení О ( n ² ), jako je například vkládání , obecně běží rychleji než bublinové řazení a nejsou o nic složitější. Řazení bublin proto není praktickým algoritmem řazení.

Jedinou významnou výhodou, kterou má bublinové třídění oproti většině ostatních algoritmů, dokonce i quicksort , ale nikoli vložení , je to, že schopnost detekovat, že je seznam seřazen efektivně, je integrována do algoritmu. Když je seznam již seřazen (nejlepší případ), složitost bublinového řazení je pouze O ( n ). Naproti tomu většina ostatních algoritmů, dokonce i těch s lepší složitostí průměrných případů , provádí celý proces třídění na sadě, a proto jsou složitější. Tuto výhodu však sdílí nejen vkládání , ale také si lépe vede na seznamu, který je podstatně seřazen (s malým počtem inverzí ). Pokud je navíc toto chování žádoucí, lze jej triviálně přidat do jakéhokoli jiného algoritmu kontrolou seznamu před spuštěním algoritmu.

Králíci a želvy

Vzdálenost a směr, které se prvky musí během řazení pohybovat, určují výkon bublinového řazení, protože prvky se pohybují v různých směrech různými rychlostmi. Prvek, který se musí přesunout na konec seznamu, se může rychle pohybovat, protože se může účastnit po sobě jdoucích swapů. Největší prvek v seznamu například vyhraje každý swap, takže se při prvním průchodu přesune do seřazené polohy, i když začíná blízko začátku. Na druhou stranu prvek, který se musí přesunout na začátek seznamu, se nemůže pohybovat rychleji než o jeden krok na průchod, takže prvky se na začátek pohybují velmi pomalu. Pokud je nejmenší prvek na konci seznamu, bude trvat n −1 průchodů, aby se přesunul na začátek. To vedlo k tomu, že tyto typy prvků byly pojmenovány králíci a želvy podle postav v Ezopově bajce O želvě a Zajíci .

Byly vyvinuty různé snahy eliminovat želvy, aby se zlepšila rychlost třídění bublin. Koktejlové třídění je obousměrné bublinové třídění, které probíhá od začátku do konce a pak se obrací, jde od začátku k začátku. Dokáže pohybovat želvami docela dobře, ale zachovává si O (n ² ) nejhorší složitost. Hřebenové řazení porovnává prvky oddělené velkými mezerami a dokáže extrémně rychle přesunout želvy, než přejde na menší a menší mezery, aby seznam vyhladil. Jeho průměrná rychlost je srovnatelná s rychlejšími algoritmy, jako je quicksort .

Podrobný příklad

Vezměte řadu čísel „5 1 4 2 8“ a pomocí bublinového řazení seřiďte pole od nejnižšího čísla k největšímu. V každém kroku se porovnávají prvky napsané tučně . Budou vyžadovány tři průchody;

První průchod

( 5 1 4 2 8) → ( 1 5 4 2 8), Zde algoritmus porovnává první dva prvky a swapy od 5> 1.

(1 5 4 2 8) → (1 4 5 2 8), prohodit od 5> 4

(1 4 5 2 8) → (1 4 2 5 8), prohodit od 5> 2

(1 4 2 5 8 ) → (1 4 2 5 8 ), Protože jsou tyto prvky již v pořádku (8> 5), algoritmus je nevymě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ěnit od 4> 2

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8 ) → (1 2 4 5 8 )

Pole je již seřazeno, ale algoritmus neví, zda je dokončen. Algoritmus potřebuje jeden další celý průchod bez jakékoli výměny, aby věděl, že je seřazen.

Třetí průchod

( 1 2 4 5 8) → ( 1 2 4 5 8)

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8 ) → (1 2 4 5 8 )

Implementace

Implementace pseudokódu

V pseudokódu může být algoritmus vyjádřen jako (pole založené na 0):

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure

Optimalizace řazení bublin

Algoritmus třídění bublin lze optimalizovat pozorováním, že n -tý průchod najde n -tý největší prvek a umístí jej na své konečné místo. Vnitřní smyčka se tedy může vyhnout pohledu na posledních n -1 položek, když běží po n -tý čas:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                swapped := true
            end if
        end for
        n := n - 1
    until not swapped
end procedure

Obecněji se může stát, že více než jeden prvek je umístěn do své konečné polohy při jediném průchodu. Zejména po každém průchodu jsou všechny prvky po posledním swapu seřazeny a není nutné je znovu kontrolovat. To umožňuje přeskočit mnoho prvků, což má za následek asi v nejhorším případě 50% zlepšení v počtu srovnání (i když žádné zlepšení v počtu swapů), a přidává velmi malou složitost, protože nový kód zahrnuje proměnnou „swapped“:

K dosažení tohoto cíle v pseudokódu lze zapsat následující:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        newn := 0
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                newn := i
            end if
        end for
        n := newn
    until n ≤ 1
end procedure

Alternativní úpravy, jako je pokus o třídění koktejlových šejkrů, aby se zlepšil výkon třídění bublin při zachování stejné myšlenky opakovaného porovnávání a záměny sousedních položek.

Použití

Bublinkové řazení. Seznam byl vynesen do kartézského souřadného systému, přičemž každý bod ( x , y ) naznačuje, že hodnota y je uložena v indexu x . Poté by byl seznam seřazen podle bublinového řazení podle hodnoty každého pixelu. Všimněte si, že největší konec se nejprve roztřídí, přičemž menším prvkům trvá přesun do správných pozic déle.

Ačkoli je bublinové třídění jedním z nejjednodušších algoritmů řazení, které je možné pochopit a implementovat, jeho složitost O ( n ² ) znamená, že jeho účinnost dramaticky klesá na seznamech více než malého počtu prvků. Dokonce i mezi jednoduché O ( n ² ) třídění algoritmů, algoritmy jako vložení třídění jsou obvykle podstatně účinnější.

Kvůli své jednoduchosti je bublinové třídění často používáno k představení konceptu algoritmu nebo třídicího algoritmu pro úvodní studenty informatiky . Někteří výzkumníci, jako například Owen Astrachan, se však snažili znevažovat bublinové třídění a jeho pokračující popularitu ve vzdělávání v informatice a doporučovali, aby se již ani nevyučoval.

Soubor Jargon , který skvěle nazývá bogosort „archetypický [sic] zvráceně hrozný algoritmus“, také nazývá bublinové řazení „obecný špatný algoritmus“. Donald Knuth v časopise The Art of Computer Programming dospěl k závěru, že „bublinové řazení podle všeho nemá co doporučit, kromě chytlavého názvu a skutečnosti, že vede k některým zajímavým teoretickým problémům“, o některých pak diskutuje.

Řazení bublin je v nejhorším případě asymptoticky ekvivalentní běhu vložení, ale tyto dva algoritmy se značně liší v počtu nezbytných swapů. Experimentální výsledky, jako jsou ty z Astrachanu, také ukázaly, že třídění vkládání funguje podstatně lépe i na náhodných seznamech. Z těchto důvodů se mnoho moderních učebnic algoritmů vyhýbá používání algoritmu bublinového řazení ve prospěch vkládání.

Bubble sort také špatně spolupracuje s moderním hardwarem CPU. Produkuje nejméně dvakrát tolik zápisů než typ vložení, dvakrát tolik chyb mezipaměti a asymptoticky více nesprávných předpovědí větví . Experimenty s Astrachanovými třídicími řetězci v Javě ukazují, že bublinové třídění je zhruba pětinové tak rychlé jako vkládací a 70% tak rychlé jako výběrové .

V počítačové grafice je třídění bublin oblíbené díky své schopnosti detekovat velmi malou chybu (jako je výměna pouze dvou prvků) v téměř tříděných polích a opravit ji pouze lineární složitostí (2 n ). Používá se například v algoritmu polygonového vyplňování, kde jsou ohraničující čáry seřazeny podle jejich souřadnice x na konkrétní skenovací linii (čára rovnoběžná s osou x ) a s přírůstkem y se jejich pořadí mění (dva prvky se prohodí) pouze v průsečíky dvou čar. Řazení bublin je stabilní algoritmus řazení, jako je vkládání.

Variace

• Odd – even sort je paralelní verze bublinového řazení pro systémy předávající zprávy.
• Průkazy mohou být zprava doleva, nikoli zleva doprava. To je efektivnější u seznamů s přidanými netříděnými položkami na konec.
• Koktejlové třepačky se střídají doleva a doprava.

Debata o jménu

Bublinkové třídění bylo příležitostně označováno jako „potápivé třídění“.

Například v knize Umění počítačového programování Donalda Knutha , svazek 3: Třídění a vyhledávání , v oddíle 5.2.1 „Řazení podle vložení“ uvádí, že [hodnota] „se ustálí na své správné úrovni“ a že tento způsob třídění má někdy se jim říkalo prosévání nebo potopení .

Tato debata je udržována snadností, s jakou lze tento algoritmus posuzovat ze dvou různých, ale stejně platných perspektiv:

1. Tyto větší hodnoty by mohly být považovány za těžší , a proto je zřejmé postupně dřezu do dolní části seznamu
2. Tyto menší hodnoty by mohly být považovány za lehčí , a proto považovat postupně bublinou až na vrchol seznamu.

V populární kultuře

V roce 2007 se bývalý generální ředitel společnosti Google Eric Schmidt zeptal tehdejšího prezidentského kandidáta Baracka Obamy během rozhovoru na nejlepší způsob třídění jednoho milionu celých čísel ; Obama se na chvíli zastavil a odpověděl: „Myslím, že bublinkové třídění by bylo špatnou cestou.“

Poznámky

Reference

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein . Úvod do algoritmů , druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN  0-262-03293-7 . Problém 2-2, str.40.
• Třídění podle předpovědi větví a mezipaměti
• Základy datových struktur Ellis Horowitz, Sartaj Sahni a Susan Anderson-Freed ISBN  81-7371-605-6
• Owen Astrachan . Bubble Sort: Archeologická algoritmická analýza

externí odkazy

• Martin, David R. (2007). „Animované algoritmy řazení: Bubble Sort“ . Archivovány od originálu na 2015-03-03. - grafická ukázka
• „Lafore's Bubble Sort“ . (Animace apletu Java)
• Sekvence OEIS A008302 (tabulka (statistika) počtu permutací [n], které během řazení potřebují k párových swapů)