Smoothsort - Smoothsort

Smoothsort
Animace zobrazující provoz smoothsortu, zobrazující hromadu, která se staví a poté rozebírá,
Smoothsort pracující na poli, které je většinou v pořádku. Pruhy v horní části ukazují stromovou strukturu.
Třída Algoritmus řazení
Datová struktura Pole
Nejhorší výkon O ( n log n )
Nejlepší výkon O ( n )
Průměrný výkon O ( n log n )
Nejhorší prostorová složitost O ( n ) celkem, O (1) pomocný

V počítačové vědě je smoothsort srovnávací algoritmus založený na srovnání . Varianta heapsortu , kterou vynalezl a publikoval Edsger Dijkstra v roce 1981. Stejně jako heapsort, smoothsort je algoritmus na místě s horní hranicí O ( n log  n ) , ale není stabilní . Výhodou smoothsortu je, že se blíží času O ( n ), pokud je vstup již do určité míry seřazen , zatímco heapsort průměruje O ( n log  n ) bez ohledu na počáteční seřazený stav.

Přehled

Stejně jako heapsort , smoothsort organizuje vstup do prioritní fronty a poté opakovaně extrahuje maximum. Podobně jako heapsort je prioritní frontou implicitní datová struktura haldy (implicitní binární strom uspořádaný hromadou ), která zabírá předponu pole. Každá extrakce zmenší předponu a přidá extrahovaný prvek do rostoucí tříděné přípony. Když se předpona zmenší na nic, je pole zcela seřazeno.

Heapsort mapuje binární strom na pole pomocí průchodu stromu shora dolů do šířky; pole začíná kořenem stromu, potom dvěma dětmi, čtyřmi vnoučaty atd. Každý prvek má přesně definovanou hloubku pod kořenem stromu a každý prvek kromě kořene má v poli svého rodiče dříve. Jeho výška nad listy však závisí na velikosti pole. To má tu nevýhodu, že každý prvek musí být přesunut v rámci procesu třídění: musí být před přesunem do svého konečného umístění procházen kořenem.

Smoothsort používá jiné mapování, procházení hloubkou zdola nahoru, první po objednávce . Po levém dítěti následuje podstrom zakořeněný u jeho sourozence a po pravém dítěti jeho rodič. Každý prvek má dobře definované výšky nad listy a každý non-leaf prvek má své děti dříve v poli. Jeho hloubka pod kořenem však závisí na velikosti pole. Algoritmus je organizován tak, že kořen je na konci haldy a v okamžiku, kdy je prvek z hromady extrahován, je již ve svém konečném umístění a není třeba jej přesouvat. Také seřazené pole je již platnou hromadou a mnoho seřazených intervalů jsou platné haldy uspořádané podstromy.

Formálněji je každá pozice i kořenem jedinečného podstromu, jehož uzly zaujímají souvislý interval, který končí na i . Počáteční předpona pole (včetně celého pole) může být takový interval odpovídající podstromu, ale obecně se rozkládá jako spojení několika po sobě následujících intervalů podstromu, které Dijkstra nazývá „úseky“. Jakýkoli podstrom bez nadřazeného prvku (tj. Zakořeněný v poloze, jejíž rodič leží mimo uvažovanou předponu) poskytuje úsek v rozkladu tohoto intervalu, přičemž tento rozklad je proto jedinečný. Když je k předponě připojen nový uzel, nastane jeden ze dvou případů: buď je pozice list a přidá k rozložení úsek o délce 1, nebo se spojí s posledními dvěma úseky a stane se rodičem příslušných kořenů, tedy nahrazení dvou úseků novým úsekem obsahujícím jejich spojení plus novou (kořenovou) polohu.

Dijkstra poznamenal, že zjevným pravidlem by bylo kombinovat úseky právě tehdy, pokud mají stejnou velikost, v takovém případě by všechny podstromy byly dokonalými binárními stromy o velikosti 2 k -1 . Zvolil však jiné pravidlo, které dává více možných velikostí stromů. To má stejnou asymptotickou účinnost , ale získává malý konstantní faktor účinnosti tím, že vyžaduje méně úseků k pokrytí každého intervalu.

Pravidlo, které Dijkstra používá, je, že poslední dva úseky jsou kombinovány právě tehdy, pokud jsou jejich velikosti po sobě jdoucí Leonardo čísla L ( i +1) a L ( i ) (v tomto pořadí), která čísla jsou rekurzivně definována, způsobem velmi podobným k číslům Fibonacci , jako:

  • L (0) = L (1) = 1
  • L ( k +2) = L ( k +1) + L ( k ) + 1

V důsledku toho je velikost jakéhokoli podstromu číslo Leonardo. Sekvenci velikostí úseků rozkládajících prvních n pozic pro libovolné n lze nalézt chamtivým způsobem: první velikost je největší Leonardovo číslo nepřesahující n a zbytek (pokud existuje) se rozloží rekurzivně. Velikosti úseků se snižují, a to striktně až na dvě konečné velikosti 1, a vyhýbají se po sobě jdoucím číslům Leonardo s výjimkou posledních dvou velikostí.

Kromě toho, že každý úsek je strom uspořádaný na hromadu, jsou kořeny stromů udržovány v seřazeném pořadí. To účinně přidá ke každému kořenu třetí dítě (kterému Dijkstra říká „nevlastní syn“) a propojí ho s předchozím kořenem. To spojuje všechny stromy dohromady do jedné globální hromady. s globálním maximem na konci.

Přestože je umístění nevlastního syna každého uzlu pevné, propojení existuje pouze pro kořeny stromů, což znamená, že odkazy jsou odstraněny vždy, když jsou stromy sloučeny. To se liší od běžných dětí, které jsou propojeny, pokud existuje rodič.

V první fázi (hromadění hromady) je stále větší počáteční část pole reorganizována tak, aby podstrom pro každý z jeho úseků byl maximální hromada: vstup v jakékoli nelistové poloze je alespoň tak velký jako záznamy na pozicích, které jsou jeho podřízenými. Kromě toho jsou všechny kořeny přinejmenším stejně velké jako jejich nevlastní synové.

Ve druhé fázi (zmenšování haldy) se maximální uzel odpojí od konce pole (aniž by bylo nutné jej přesouvat) a mezi jeho potomky se obnoví invarianty haldy. (Konkrétně mezi nově vytvořenými nevlastními syny.)

Praktická implementace často vyžaduje výpočet Leonardových čísel L ( k ) . Dijkstra poskytuje chytrý kód, který využívá pevný počet celočíselných proměnných k efektivnímu výpočtu hodnot potřebných v době, kdy jsou potřeba. Alternativně, pokud existuje konečná mezní hodnota N o velikosti polí, která mají být tříděna, lze předpočítanou tabulku čísel Leonardo uložit do prostoru O (log  N ) .

Operace

Zatímco dvě fáze postupu třídění jsou si navzájem opačné, pokud jde o vývoj struktury sekvence haldy, jsou implementovány pomocí jednoho jádrového primitiva, ekvivalentního operaci „prosít dolů“ v binárním max. halda.

Prosévání dolů

Operace procházení jádra (kterou Dijkstra nazývá „ trinkl “) obnoví invariant haldy, pokud je případně narušen pouze v kořenovém uzlu. Pokud je kořenový uzel menší než kterýkoli z jeho podřízených, je prohozen s největším podřízeným a proces se opakuje s kořenovým uzlem v jeho novém podstromu.

Rozdíl mezi smoothsort a binární max-haldou je v tom, že kořen každého úseku musí být uspořádán s ohledem na třetí „nevlastního syna“: kořen předchozího úseku. Procedura prohledávání tedy začíná sérií čtyřcestných srovnání (kořenový uzel a tři děti), dokud nevlastní syn není maximálním prvkem, pak série třícestných srovnání (kořen plus dvě děti) až do kořene uzel najde svůj konečný domov a invarianty se obnoví.

Každý strom je úplný binární strom : každý uzel má dvě podřízené nebo žádné. Není třeba řešit speciální případ jednoho dítěte, ke kterému dochází ve standardní implicitní binární hromadě . (Zvláštní případ nevlastního syna však toto ukládání více než jen kompenzuje.)

Protože existují úseky O (log  n ) , z nichž každý je stromem hloubky O (log  n ) , je čas na provedení každé operace prosévání ohraničen O (log  n ) .

Pěstování oblasti haldy začleněním prvku doprava

Když se uvažuje o začlenění dalšího prvku do sekvence úseků (seznam disjunktních struktur haldy), buď vytvoří nový úsek jednoho prvku, nebo kombinuje dva úseky zcela vpravo tím, že se stane rodičem obou jejich kořenů a vytvoří nový úsek který nahradí dva v pořadí. Který z těchto dvou případů se stane, závisí pouze na velikosti aktuálně přítomných úseků (a nakonec pouze na indexu přidaného prvku); Dijkstra stanovil, že úseky jsou kombinovány tehdy a jen tehdy, jsou -li jejich velikosti L ( k +1) a L ( k ) u některých k , tj. Po sobě jdoucích čísel Leonarda; nový úsek bude mít velikost L ( k +2) .

V obou případech musí být nový prvek proset na správné místo ve struktuře haldy. I když je nový uzel jednoprvkový úsek, musí být stále řazen relativně ke kořenu předchozího úseku.

Optimalizace

Algoritmus Dijkstra šetří práci tím, že pozoruje, že na konci rostoucí fáze je vyžadována celá hromada invariantu, ale není vyžadována v každém mezistupni. Zejména požadavek, aby byl prvek větší než jeho nevlastní syn, je důležitý pouze pro prvky, které jsou konečnými kořeny stromů.

Když je tedy prvek přidán, vypočítejte polohu jeho budoucího rodiče. Pokud je to v rozsahu zbývajících hodnot, které mají být tříděny, chovejte se, jako by neexistoval žádný nevlastní syn, a sledujte pouze aktuální strom.

Zmenšení oblasti haldy oddělením prvku úplně vpravo od ní

Během této fáze forma posloupnosti úseků prochází změnami rostoucí fáze obráceně. Při oddělování listového uzlu není nutná žádná práce, ale pro nelistový uzel se jeho dvě děti stávají kořeny nových úseků a je třeba je přesunout na správné místo v pořadí kořenů úseků. Toho lze dosáhnout dvojitým prosetím: nejprve pro levé dítě a poté pro pravé dítě (jehož nevlastním synem bylo levé dítě).

Protože polovina všech uzlů v úplném binárním stromu jsou listy, provede se v průměru jedna operace třídění dolů na uzel.

Optimalizace

Je již známo, že nově odhalené kořeny jsou správně uspořádány s ohledem na jejich normální děti; jde pouze o uspořádání vzhledem k jejich nevlastním synům. Proto při zmenšování haldy lze první krok prosévání zjednodušit na jediné srovnání se nevlastním synem. Pokud dojde k výměně, musí následující kroky provést úplné čtyřsměrné srovnání.

Analýza

Smoothsort potřebuje O ( n ) čas na zpracování předřazeného pole, O ( n log  n ) v nejhorším případě a dosahuje téměř lineárního výkonu na mnoha téměř tříděných vstupech. Nezpracovává však optimálně všechny téměř seřazené sekvence. Použití počet inverzních jako míra un-sortedness (počet párů indexy i a j s i < j a A [ i ]> [ j ] , nebo náhodně seřazené vstupu je to přibližně n 2 /4 ), existují možné vstupní sekvence s inverzemi O ( n log  n ), které způsobují, že zabere čas Ω ( n log  n ) , zatímco jiné adaptivní algoritmy řazení mohou tyto případy vyřešit v čase O ( n log log  n ) .

Algoritmus smoothsort musí být schopen uchovat v paměti velikosti všech stromů v haldě Leonardo. Protože jsou seřazeny podle pořadí a všechny objednávky jsou odlišné, obvykle se to provádí pomocí bitového vektoru , který označuje, jaké objednávky jsou přítomny. Navíc, protože největší řád je nejvýše O (log  n ) , lze tyto bity zakódovat do strojových slov O (1) za předpokladu transdichotomického modelu stroje .

Všimněte si, že strojová slova O (1) nejsou totéž jako jedno strojové slovo. 32bitový vektor by stačil pouze pro velikosti menší než L (32) = 7049155 . 64bitový vektor bude stačit pro velikosti menší než L (64) = 34335360355129 ≈ 2 45 . Obecně platí, že na bit velikosti je potřeba 1/log 2 ( φ ) ≈ 1,44 bitů vektoru.

Topol

Jednodušší algoritmus inspirovaný smoothsortem je topolové třídění . Pojmenovaný podle řad stromů s klesající velikostí, které jsou často pozorovány v nizozemských poldrech , provádí méně srovnání než smoothsort pro vstupy, které nejsou většinou tříděny, ale nemohou dosáhnout lineárního času pro tříděné vstupy.

Významná změna provedená topolovým tříděním v tom, že kořeny různých stromů nejsou udržovány v seřazeném pořadí; neexistují žádné odkazy „nevlastního syna“, které by je spojovaly do jedné hromady. Místo toho pokaždé, když se hromada ve druhé fázi zmenší, prohledají se kořeny, aby se našel maximální záznam.

Protože existuje n zmenšovacích kroků, z nichž každý musí maximálně vyhledat kořeny stromu O (log  n ) , je nejlepší doba běhu pro topolové řazení O ( n log  n ) .

Autoři také navrhují použít k dalšímu zjednodušení spíše dokonalé binární stromy než stromy Leonardo, ale toto je méně významná změna.

Stejná struktura byla navržena jako prioritní fronta pro obecné účely pod názvem halda po objednávce , dosahující amortizovaného času vložení O (1) do struktury jednodušší než implicitní binomická hromada .

Aplikace

Knihovna musl C ke své implementaci používá smoothsort qsort().

Reference

externí odkazy