Adaptivní řazení - Adaptive sort - Wikipedia

A třídicí algoritmus spadá do adaptivní druh rodina, pokud ve svém vstupu využije stávající objednávky. Využívá výhod přednastavení ve vstupní sekvenci - nebo omezeného množství porucha pro různé definice měr poruchy - a třídí se rychleji. Adaptivní třídění se obvykle provádí úpravou stávajících třídicích algoritmů.

Motivace

Porovnávací algoritmy řazení se tradičně zabývají dosažením optimální hranice Ó (n log n) při jednání s časová složitost. Adaptivní řazení využívá stávajícího pořadí vstupu k pokusu o dosažení lepších časů, takže čas potřebný k třídění algoritmem je plynule rostoucí funkcí velikosti sekvence a porucha v pořadí. Jinými slovy, čím více je vstup předem roztříděn, tím rychleji by měl být tříděn.

Toto je atraktivní algoritmus, protože téměř seřazené sekvence jsou v praxi běžné. Výkon stávajících algoritmů řazení lze tedy zlepšit zohledněním stávajícího pořadí ve vstupu.

Všimněte si, že většina algoritmů řazení v nejhorším případě, které se v tom nejhorším případě optimálně daří, zejména hromada třídění a Sloučit třídění, nebere v úvahu stávající pořadí v rámci jejich vstupu, ačkoli tento nedostatek lze snadno napravit v případě Sloučit třídění kontrolou, zda je poslední prvek levé skupiny menší než (nebo rovný) prvnímu prvku pravé skupiny, v takovém případě může být slučovací operace nahrazena jednoduchým zřetězením - modifikace, která je v rozsahu tvorby algoritmus adaptivní.

Příklady

Klasickým příkladem adaptivního třídicího algoritmu je Přímé řazení. V tomto algoritmu řazení skenujeme vstup zleva doprava, opakovaně nacházíme pozici aktuální položky a vkládáme ji do pole dříve seřazených položek.

v pseudo kód forma, Přímé řazení algoritmus může vypadat nějak takto (pole X je založeno na nule):

postup Přímé řazení (X): pro j: = 1 na délka (X) - 1 dělat        t: = X [j] i: = j zatímco i> 0 a X [i - 1]> t dělat            X [i]: = X [i - 1] i: = i - 1 konec        X [i]: = t konec

Výkon tohoto algoritmu lze popsat z hlediska počtu inverze ve vstupu a poté bude zhruba rovno , kde je počet inverzí. Pomocí této míry předtříděnosti - vzhledem k počtu inverzí - Přímé řazení třídění trvá méně času, tím blíže k třídění.

Další příklady algoritmů adaptivního řazení jsou adaptivní třídění haldy, adaptivní třídění sloučení, druh trpělivosti,[1] Shellsort, smoothsort, splaysort a Timsort.[1]

Viz také

Reference

  • Hagerup, Torben; Jyrki Katjainen (2004). Teorie algoritmů - SWAT 2004. Berlin Heidelberg: Springer-Verlag. str. 221–222. ISBN  3-540-22339-8.
  • Mehta, Dinesh P .; Sartaj Sahni (2005). Datové struktury a aplikace. USA: Chapman & Hall / CRC. str. 11‑8–11‑9. ISBN  1-58488-435-5.
  • Estivill-Castro, Vladmir; Dřevo, Dericku (Prosinec 1992). Msgstr "Průzkum algoritmů adaptivního třídění". ACM. New York, NY, USA. 24 (4): 441–476. CiteSeerX  10.1.1.45.8017. doi:10.1145/146370.146381. ISSN  0360-0300. S2CID  1540978.
  • Petersson, Ola; Alistair Moffat (1992). "Rámec pro adaptivní třídění". Přednášky z informatiky. 621. Berlín: Springer Berlin / Heidelberg: 422–433. doi:10.1007/3-540-55706-7_38. ISBN  978-3-540-55706-7. ISSN  1611-3349. Citovat deník vyžaduje | deník = (Pomoc)
  1. ^ A b Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (PDF). SIGMOD / PODS.