Diskuse:Rychlé řazení

Domnívám se, že výraz třídit [1] sice není úplně nejpřesnější, ale přesto se používá významně častěji něž výraz řadit [2]. --Pastorius

Jaký je v tom rozdíl? My tomu vždycky říkali třídící algoritmy. --Egg ✉ 10:38, 14. 4. 2006 (UTC)

@Egg: Třídicí algoritmus data třídí, „dělí do tříd“, tzn. seskupuje data do skupin sdílejících nějakou vlastnost, přičemž vzájemné uspořádání různých skupin je nepodstatné (ba nemusí být ani součástí výstupu). Řadicí algoritmus data řadí, tzn. vytváří posloupnost uspořádanou podle velikosti (přičemž vzájemné uspořádání prvků stejné velikosti je relativně nepodstatné).

@Pastorius: Google jsem zkoušel ještě před změnou a převaha třídění nad řazením mi nepřijde jako natolik zásadní. Mimochodem úplně nejčastější jsou zřejmě „třídící algoritmy“, což je výraz chybný nejen věcně, ale i jazykově, jak se snad shodneme (když už se na tom, zdá se, neshodneme s Eggem).

--Mormegil ✉ 10:59, 14. 4. 2006 (UTC)

Pro mně, klasifikační algoritmy "dělí klasifikují do tříd". Jj14 (diskuse) 17. 7. 2014, 08:26 (UTC)

No tak dnes už je častější "řazení", než třídění ;) Často jsem spíše pro zachování tradičních pojmů, zvl. když je to "terminus technicus" vycházející z angličtiny. Například dávám přednost "adresáři" před "složkou", nebo "bytu" před "bajtem". Asi budu ze setrvačnosti psát "třídění", ale z jazykového hlediska je "řazení" skutečně lepší, intuitivně lépe pochopitelný pojem. --Pteryx 3. 3. 2011, 17:24 (UTC)

C vs. Pascal vs. Haskell

Návrh na zrušení céčkového kódu nepřijímám (viz. úpravy Mormegilla), pro céčkaře je jistě stravitelnější :) Uznávám, že Pascal je obecně čitelnější. C-jazyk zase existuje pro každé CPU na které si vzpomenete a z jeho syntaxe vychází hromada dalších jazyků. Co se týče Haskellu, není to ani přehnaně čitelný, a zatím ani příliš známý jazyk. --Pteryx (diskuse) 20. 5. 2013, 11:11 (UTC)

Rekurzivní a nerekurzivní verze

Algoritmus je v každém případě dobré ošetřit proti hluboké rekurzi. To se dělá tím, že se po pivotizaci volá volá rekurzivně pro menší část rozděleného pole a větší část se řadí nerekurzivně. Nebo se tam dá přidat pomocné pole ve funkci zásobníku. V tom případě na zásobník odložíme větší část posloupnosti a tu menší vytřídíme v cyklu. Tohle řešení publikoval Wirth a já uznávám že je efektivnější a nic proti němu nenamítám.

To omezení rekurze někdo poškrtal, ale to je taky správně! Ve skutečnosti v tom není rozpor. Když zavoláte rekurzi pro menší část pole, tak procesor uloží na systémový zásobník stav lokálních proměnných (tj. hranice větší části rozděleného pole!) a menší část pole seřadí hned - je to stejné! Nebo jinak. Když volám rekurzi pro menší část pole, tak je to vždy "menší polovina", tzn. počet zanoření je maximálně dvojkový logaritmus počtu prvků (plusmínus jedna, jak to v životě někdy chodí). Chce to nasadit myslící čapku.

Upřímně řečeno, čím déle studuji quicksort, tím více oceňuji genialitu heapsortu. Akorát mě dráždilo, že jsem ho nechápal. Jestli budete děti hodné, tak se ten heapsort pokusím tetě Wiki vysvětlit ;) --Pteryx (diskuse) 15. 8. 2014, 16:19 (UTC)

(To já loupal perníček, asi.) To, co popisujete, je už asi měsíc v textu o odstavec dál - jak nejlépe, stručně a obecně jsem uměl. Pro jistotu: Tato optimalizace je o pořadí vyhodnocování, tj. o tom, co se ukládá, vybírá a neukládá na zásobník, a nezávisí na rekurzi, tj. jde implementovat rekurzivně i nerekurzivně. To jsem chtěl v textu oddělit. -- Jj14 (diskuse) 22. 8. 2014, 22:51 (UTC)

C a C++

Pozor na rozdíly mezi C a C++, obecné C nedovoluje definice proměnných uprostřed kódu (opravil jsem to).

Haskell

Často se uvádí následující implementace v Haskellu, která byla uvedena i na stránce Quicksortu.

    quicksort :: (Ord a) => [a] -> [a]
    quicksort [] = []
    quicksort (x:xs) = quicksort(filter (<x) xs) ++ x:quicksort(filter (>=x) xs)

Je sice lákavé mít možnost napsat quicksort na 2 řádky, ale toto bohužel není quicksort. Skutečný quicksort využívá chytrého přehazování prvků v paměti, což se v tomto případě neděje. Tato implementace má paměťové nároky srovnatelné s mergesortem. Z tohoto důvodu jsem tento matoucí kód ze stránky odebral.

Skutečný Quicksort to je, protože jádrem algoritmu je rozdělení pole podle pivota. Ale je pravda, že taková implementace výhody Quicksortu poněkud degraduje. --Pteryx (diskuse) 20. 5. 2013, 11:11 (UTC)

Posedlost rychlostí

Mám takový pocit, že všichni jsou posedlí tím aby to fungovalo "co nejrychleji". Vždyť kompatibilitu nám přece vyřeší Java, že? Jsou sice určité drobné rozdíly například v FPU, (která se *musí* používat, aby to bylo rychlé), ale ty se nějak vstřebají, většinou. Tož nebuďme škarohlídi. Ale abychom Javu mohli použít, tak potřebujeme co nejrychleší algoritmy a s malou spotřebou paměti, protože je to bazmek dynamický, objektový, s garbage collectorem, žrout paměti a strojového času. A tak použijeme quicksort. Protože všechno už před námi udělal někdo jiný (a jistě daleko lépe než my, žejo?), tak tam vrazíme knihovní funkci. A kde potom máte reprodukovatelnost výsledků a kompatibilitu? Legrační na celé věci je, že tu knihovní funkci jistě používá hromada jiných knihovních funkcí, které musíte používat a jejichž chod vůbec nemůžete ovlivnit ...

Prosímvás, kdo píšete články o programování, zkuste se nad tím zamyslet, rychlost zdaleka (ba ani většinou) není všechno. --Pteryx 3. 3. 2011, 19:02 (UTC)

Ale ty nevýhody jako nestabilita tam jsou, chybí-li ti něco tak to tam dopiš. Zagothal 21. 3. 2011, 13:36 (UTC)

Presne tak. Pokud citite potrebu nejakeho doplneni, v kreativite nejsou meze kladeny. Editujte s odvahou :-) --Maertien 6. 5. 2011, 13:11 (UTC)

Upřímně řečeno nechápu, o co vám jde. Nikdo nikde netvrdí, že rychlost je v programování to nejdůležitější a co má Quicksort společného s Javou taky netuším. --Adam Zivner 9. 5. 2011, 11:21 (UTC)

Vadí mi, když někdo do nebe vynáší nějaký algoritmus, aniž by se zmínil o tom, že má několik vyloženě zákeřných rysů. Vadí mi, že jediným kritériem hodnocení algoritmů je rychlost. Quicksort v nepříznivém případě vyžaduje spoustu paměti skryté v rekurzivním volání funkcí. U embedded systémů s malým zásobníkem umístěným většinou přímo ve vnitřní RAM CPU je to tragický nedostatek. Jazyku Java se omlouvám, ten za to opravdu nemůže a Sun-ovské standardní knihovny jsou jistě implementovány korektně. --95.82.190.20 15. 5. 2011, 22:23 (UTC)

Vidím/cítím (a opravuji) v textu jiný problém: nerozlišuje se mezi naivním vysvětlením algoritmu a dobrou implementací (argumentační klam "figurína"). Když chci, aby to bylo rychlé nebo paměťově skromné, tak musím použít vhodnou, například optimalizovanou, verzi a ne Rychlý Úvod do pomalého quicksortu pro manažery a BFU. Týká se to i embedded systémů; ale možná tam je i jiný problém (nejsem expert). (Rekurzivně, číst se to dá, ale na úplně jiné úrovni vnímání. :-))

@Pteryx: Myslím, že implementační triky k vysvětlení patří. Jsou použitelné obecně (nejen v Javě), i když ne vždy (Haskell). Jj14 (diskuse) 17. 7. 2014, 09:14 (UTC)

Vážně nechápu, proč vadí decentní upozornění na nedostatky quicksortu, nebo na díry a nekonzitence vedoucí k nekompatibilitě systémů. Jestli chcete do článku nějaké implementační triky dopsat, máte možnost, naznačil jsem cestu. Ale na vašem místě bych to nedělal. Chytrému napověz a těmi ostatními se nemá smysl zabývat. --Pteryx (diskuse) 15. 8. 2014, 08:46 (UTC)

Nevadí mi upozornění na nedostatky. Ale chci rozlišit, co je "neodstranitelný" nedostatek algoritmu (například nestabilní řazení) a co je nevhodná/naivní implementace. Protože toto rozlišení mi připadalo v textu vágní, tak jsem tak přidával ty "implementační triky" (teda spíš jeden, a snažil se zdůraznit jejich podstatu). Pokud můžu ^napovědět "po lopatě", tak to udělám (někdy přeformuluji, někdy nepochopím/nevystihnu původní myšlenku - ale tento článek dřív obsahoval jasné nesmysly). Obecně, nejen pro quicksort: "Každý ^bazmek lze použít nevhodně." Pro informaci: kolik zásobníku mají embedded procesory? -- Jj14 (diskuse) 22. 8. 2014, 23:44 (UTC)

Podstatné je, že Vaše úpravy byly podloženy znalostí podstaty věci a přispěly ke zdokonalení článku. Bylo by možné do článku nacpat celý algoritmus s úpravou proti přetečení zásobníku, ale byl by dvakrát delší než ten co tam je teď a nevím jak bych to encyklopedicky doložil. Co se týče embedded CPU, velikost systémového zásobníku začíná na několika bajtech (PIC), o qsortu by se dalo uvažovat už u mašinek co mají systémový zásobník řádově jeden až několik kilobajtů. --Pteryx (diskuse) 2. 9. 2014, 09:04 (UTC)

A další

1. Píše se: "... může prostoduchá implementace quicksortu vést dokonce i k přeplnění zásobníku a pádu programu."

refaktorizovánoUff, proč si všichni myslí, že pády programu jsou něco naprosto normálního. Vždyť je to stejný problém jako výše, daný nesprávnou implementací, zde neošetřením přetečení zásobníku. A v důsledku je jedno, zda to bylo z nedostatku času, paměti, peněz nebo vědomostí nebo to šéf manager zakázal. --Jj14 (diskuse) 22. 7. 2014, 12:17 (UTC)

No jo, vadí Vám že jsem to napsal. Když neprovedeme analýzu spotřeby systémových prostředků, tak se můžeme spálit. Bez ohledu na to jak "ošetříme" přetečnení zásobníku, tak ta aplikace prostě v nepříznivém případě nemusí fungovat. Strojový čas, paměť, i trpělivost šéfů jsou vždy nějak omezené. Smiřte se s tím. --Pteryx (diskuse) 15. 8. 2014, 08:43 (UTC)

2. příklad o hloubce zásobníku reaguje na výhrady v textu v dnešní verzi. Možná tam nepatří v této podobě. Možná má někdo lepší nápad, co s tím. --Jj14 (diskuse) 22. 7. 2014, 12:44 (UTC)

Externí odkazy či reference byly změněny (září 2018)

Dobrý den,

právě jsem se pokusil opravit 2 externí odkazy či reference na stránce Quicksort. Prosím, zkontrolujte moje editace. Pokud máte nějaké otázky, potřebujete, abych tyto odkazy nebo dokonce celou tuto stránku ignoroval, prosím vizte seznam často kladených otázek pro další informaci. Provedl jsem následující změny:

• Přidán odkaz na https://web.archive.org/web/20051124012106/http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort do http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort
• Opraveno formátování u http://www.mycsresource.net/articles/programming/sorting_algos/quicksort

. Udělal-li jsem chybu, vizte seznam často kladených otázek.

Děkuji.—InternetArchiveBot (Nahlásit chybu) 3. 9. 2018, 05:48 (CEST)

České Názvosloví

@Pavouk: Pod rychlým řazením si představím automatickou spojku a šlápnutí na plyn - tam je to očekávaný název. Pod rychlým tříděním si představím libovolný subkvadratický algoritmus třídění. Quicksort je quicksort. A v kategorii Kategorie:Řadicí algoritmy se nedá nic očekávaného najít, jak už jsem psal jinde. Jj14 (diskuse) 29. 9. 2023, 18:17 (CEST)