Stooge třídění - Stooge sort - Wikipedia

Stooge třídění

Vizualizace řazení Stooge (zobrazuje pouze swapy).
Třída	Algoritmus řazení
Datová struktura	Pole
Nejhorší případ výkon	Ó(nlog 3 / log 1.5)
Nejhorší případ složitost prostoru	Ó(n)

Stooge třídění je rekurzivní třídicí algoritmus. Je pozoruhodné jeho mimořádně špatným časová složitost z Ó (n^{log 3 / log 1.5} ) = O (n^2.7095...)Doba chodu algoritmu je tedy pomalejší ve srovnání s rozumnými třídicími algoritmy a je pomalejší než Třídění bublin, kanonický příklad poměrně neúčinného druhu. Je však efektivnější než Slowort. Jméno pochází z Tři loutky.^[1]

Algoritmus je definován takto:

• Pokud je hodnota na začátku větší než hodnota na konci, vyměňte je.
• Pokud jsou v seznamu 3 nebo více prvků, pak:
  • Stooge seřadí počáteční 2/3 seznamu
  • Stooge seřadí poslední 2/3 seznamu
  • Stooge znovu seřadí počáteční 2/3 seznamu

Je důležité získat celočíselnou velikost řazení použitou v rekurzivních voláních zaokrouhlením 2/3 nahoru, např. zaokrouhlení 2/3 z 5 by mělo dát 4 spíše než 3, protože jinak může řazení selhat u určitých dat.

Implementace

 funkce stoogesort(pole L, i = 0, j = délka(L)-1){     -li L[i] > L[j] pak       // Pokud je prvek nejvíce vlevo, je větší než prvek zcela vpravo         L[i] ↔ L[j]           // Zaměňte prvek úplně vlevo a úplně vpravo     -li (j - i + 1) > 2 pak       // Pokud jsou v poli alespoň 3 prvky         t = podlaha((j - i + 1) / 3)         stoogesort(L, i  , j-t)  // Seřaďte první 2/3 pole         stoogesort(L, i+t, j)    // Seřaďte poslední 2/3 pole         stoogesort(L, i  , j-t)  // Seřaďte znovu první 2/3 pole     vrátit se L }

Reference

Zdroje

• Černý, Paul E. "loutka třídění". Slovník algoritmů a datových struktur. Národní institut pro standardy a technologie. Citováno 18. června 2011.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „Problém 7-3“. Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. 161–162. ISBN  0-262-03293-7.

externí odkazy

• Algoritmy řazení (včetně třídění Stooge)
• Stooge sort - implementace a srovnání

Tento počítačová věda článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.