Částečné třídění - Partial sorting

v počítačová věda, částečné třídění je uvolněný varianta třídění problém. Celkovým tříděním je problém vracet seznam položek tak, aby se všechny jeho prvky zobrazovaly v pořadí, zatímco částečné třídění vrací seznam k nejmenší (nebo k největší) prvky v pořadí. Ostatní prvky (nad k nejmenší) mohou být také tříděny, jako v částečném řazení na místě, nebo mohou být zahozeny, což je běžné při streamování částečných druhů. Běžným praktickým příkladem částečného třídění je výpočet „Top 100“ nějakého seznamu.

Pokud jde o indexy, v částečně seřazeném seznamu pro každý index i od 1 do k, the i-tý prvek je na stejném místě, jako by byl v plně seřazeném seznamu: prvek i částečně seřazeného seznamu obsahuje statistika objednávky i seznamu vstupů.

Offline problémy

Haldy založené řešení

Hromady připustit jednoduché jednoprůchodové částečné třídění, když k je opraveno: vložte první k prvky vstupu do hromady max. Poté proveďte jeden průchod přes zbývající prvky, postupně přidejte každý do haldy a odeberte největší prvek. Každá operace vložení trvá Ó(log k) čas, což má za následek Ó(n log k) celkový čas; tento algoritmus je praktický pro malé hodnoty k a v online nastavení.[1] Další možností je vytvořit minheap pro všechny hodnoty (sestavení trvá Ó(n)) a vyjměte hlavu haldy K krát, každá operace odebrání trvá Ó(log n). V takovém případě algoritmus trvá Ó(n + klog n).

Řešení rozdělením výběru

Další relaxace vyžadující pouze seznam k nejmenší prvky, ale aniž by bylo nutné je objednávat, činí problém ekvivalentním výběr na základě oddílů; původní dílčí problém třídění lze vyřešit takovým výběrovým algoritmem, abychom získali pole, kde je první k prvky jsou k nejmenší a jejich třídění za celkovou cenu Ó(n + k log k) operace. Populární volbou pro implementaci tohoto schématu algoritmu je kombinace rychlý výběr a quicksort; výsledek se někdy nazývá „quickselsort“.[1]

Specializované třídicí algoritmy

Účinnější než výše uvedené jsou specializované algoritmy částečného třídění založené na Sloučit třídění a quicksort. Ve variantě quicksort není nutné rekurzivně třídit oddíly, které obsahují pouze prvky, které by spadaly za k'místo v konečném seřazeném poli (počínaje od "levé" hranice). Pokud tedy čep spadne na své místo k nebo později se opakujeme pouze na levém oddílu:[2]

funkce partial_quicksort (A, i, j, k) je    -li i pak        p ← pivot (A, i, j) p ← oddíl (A, i, j, p) partial_quicksort (A, i, p-1, k) -li p pak            partial_quicksort (A, p + 1, j, k)

Výsledný algoritmus se nazývá částečný quicksort a vyžaduje očekávaný pouze čas Ó(n + k log k), a je v praxi docela efektivní, zvláště pokud a výběr řazení se používá jako základní případ, když k ve srovnání s n. Nejhorší časová složitost je však stále velmi špatná, v případě špatného výběru otočného čepu. K získání lepšího výkonu v nejhorším případě lze použít výběr otáčení podle linií algoritmu lineárního výběru času v nejhorším případě.

Inkrementální třídění

Inkrementální třídění je „online“ verzí problému částečného třídění, kde je vstup zadán předem, ale k není známo: vzhledem k k-tříděné pole, mělo by být možné rozšířit částečně tříděnou část tak, aby se pole stalo (k+1)-tříděné.[3]

Hromady vést k Ó(n + k log n) řešení online částečného třídění: první „heapify“, v lineárním čase, kompletní vstupní pole k vytvoření min haldy. Poté extrahujte minimum haldy k krát.[1]

Úpravou rychlého výběru lze získat různé přírůstkové řazení. Verze kvůli Paredes a Navarro udržuje a zásobník otočných bodů mezi hovory, takže přírůstkové třídění lze dosáhnout opakovaným vyžádáním nejmenší položky pole A z následujícího algoritmu:[3]

Algoritmus IQS (A : pole, i : integer, S : zásobník) vrátí inejmenší prvek v A

  • Li i = nahoře (S):
    • Pop S
    • Vrátit se A[i]
  • Nechat pivot ← náhodný [i, horní(S))
  • Aktualizace pivot ← oddíl (A[i : horní(S)), A[pivot])
  • Tlačit pivot na S
  • Vrátit se IQS (A, i, S)

Zásobník S je inicializován tak, aby obsahoval pouze délku n z A. k-třídění pole se provádí voláním IQS (A, i, S) pro i = 0, 1, 2, ...; tato posloupnost hovorů má průměrná složitost Ó(n + k log k), což je asymptoticky ekvivalentní Ó(n + k log n). Nejhorší čas je kvadratický, ale lze to opravit nahrazením náhodného otočného výběru znakem medián mediánů algoritmus.[3]

Podpora jazyků / knihoven

Viz také

Reference

  1. ^ A b C Conrado Martínez (2004). Při částečném třídění (PDF). 10. seminář o analýze algoritmů.
  2. ^ Martínez, Conrado (2004). Částečný quicksort (PDF). Proc. 6. workshop ACM-SIAM o inženýrství a experimentech s algoritmy a 1. workshop ACM-SIAM o analytické algoritmice a kombinatorice.
  3. ^ A b C Paredes, Rodrigo; Navarro, Gonzalo (2006). Msgstr "Optimální přírůstkové třídění". Proc. Osmý workshop o algoritmickém inženýrství a experimentech (ALENEX). 171–182. CiteSeerX  10.1.1.218.4119. doi:10.1137/1.9781611972863.16. ISBN  978-1-61197-286-3.

externí odkazy