Diskuze – Lekce 6 - Quick sort

proc se nepouziva casteji merge sort, kdyz ma stejnou rychlost i stabilitu, ale navic je u nej 100% ze bude mit slozitos O {n*log(n)}, narozdil od quick sortu, kde to muze spadnout na n2

Merge sort a quicksort mají stejnou časovou složitost. To znamená, že od určitého počtu prvků jsou stejně rychlé. Na malých polích ale quicksort vychází lépe a proto je to nejčastěji volený algoritmus.

jak se vlastne ta slozitos meri? resp. kdyz rikas, ze na male pole je quicksort rychlejsi nez merge, rikas tim o kolik milisekund se provede trideni rychleji? nebo jakym zpusobem se meri (resp co je vysledek mereni), a jake jednotky. dik

Ahoj. Složitost se měří obecně (jako abstrakce slouží Turingův stroj, ale to je už trochu komplikované). Obecně se vezme časově nejnáročnější operace (což je v tomto případě porovnání / přesun prvků) a počítá se, kolikrát je operace provedena.
Dále můžeš rozlišovat složitost v nejlepším případě, v nejhorším případě a v průměru. Dále existuje i složitost asymptotická (průměrná složitost při velkém množství operací, ale ta se u třídících algoritmů moc nepoužívá).
Složitost neudává nic o reálné rychlosti. Na některém stroji může běžet sekundu a na některém minutu. Důležité je, že pro velké množství prvků, bude vždy O(n*log n) lepší než O(n²). Pro příklad seřazení 10 hodnot trvá bubblesortem 10ms a quicksortem 20ms. Ale pro 10000 hodnot to bude bubblesortem 10000ms a quicksortem 1000ms (čísla jsem si vymyslel).
Jak říkáš, quicksort je v průměrném případě nejlepší třídící algoritmus, ale v nejhorším je složitost n², proto většina implementací má tzv. fallback, který přepne na jiný třídící algoritmus, pokud se situace zdá být špatná.
Mergesort má nevýhodu, že není inplace, tedy potřebuješ alokovat větší paměťové místo (tj. má paměťovou složitost větší než quicksort), ale je stabilní.
Mergesort lze dále použít pro spojové seznamy (poté lze přepsat na inplace verzi) a pro třídění velkých dat (jelikož nemusí být všechny data uložené v paměti.
Quicksort je by default nestabilní (lze implementovat i stabilní verzi) a je inplace.
Třetím často používaným algoritmem je heapsort, která není stabilní, ale je zaručena složitost O(n*log n). V průměru má o něco horší složitost než pro quicksort (má vyšší konstantu složitosti).
Výběr ideálního třídícího algoritmu tedy závisí na situaci.

fakt moc diky za takove lidi. Ted je mi to zase o neco vice jasnejsi. Rad bych se prece jen jeste zeptal (snad uz nepusobim doterne, vim, hodne se ptam), na onu stabilitu. Tedy rozdil mezi stabilni a nestabilni nebo jak to co to vlastne je (kdyz pises, ze quicksort je defaulnute nestabilno, ale da se stabilizovat). a za 2) u mergesort rozumim spojovym zaznamum (ktera se na sebe referuji), ale nerozumim, jak to, ze by data nemusela byt ulozena v pameti, jak jinak by k nim mel pristup (prece i ty zaznamy jsou fyzicky v pameti). Jinak jeste jednou diky za vysvetleni

Stabilita, časová složitost a všechny podobné pojmy jsou vysvětleny v úvodních článcích v sekci s algoritmy. Z tvých dotazů to vypadá, že jsi je nečetl - www.itnetwork.cz/algoritmy

Stabilita znamená, že prvky se stejnou hodnotou budou mít stejné pořadí jako v neseřazené sekvenci. Například série [{k:1, v:5}, {k:2, v:4}, {k:1, v:2}] bude při stabilním řazení podle k vždy [{k:1, v:5}, {k:1, v:2}, {k:2, v:4}].
U mergesortu pracuješ s tím, že máš dvě seřazené sekvence a ty spojuješ. Například 1, 3, 9 a 2, 4, 6. Pro nejnižší prvek nemusíš znát, co následuje za 1 nebo 2. Nejenže data nepotřebuješ mít v paměti (ale mohou být například v souboru na disku), ale nepotřebuješ ani náhodný přístup (postačí sekvenční). Z tohoto důvodu byl megesort používán za dob páskových pamětí, které měli jen sekvenční přístup.

a=[1, *, *]     b=[2, *, *]     sorted=[]
a=[3, *]        b=[2, *, *]     sorted=[1]
a=[3, *]        b=[4, *]        sorted=[1, 2]
a=[9]           b=[4, *]        sorted=[1, 2, 3]
a=[9]           b=[6]           sorted=[1, 2, 3, 4]
a=[9]           b=[]            sorted=[1, 2, 3, 4, 6]
a=[]            b=[]            sorted=[1, 2, 3, 4, 6, 9]

Podmienka rekurzie, ktorú máš v zdrojovom kóde

(right >= left)

je pravdivá aj pre jednoprvkové pole.
A ako už vieme, jednoprvkové pole je triviálne zotriedené.
Nemá to byť náhodou takto:

(right > left)

???

Teda, kluci se při natáčení videí asi dobře zasmáli. 🙂

U vizualizace dle mě chybí krok zpět, aby bylo možno lépe pochopit, jak to funguje a mohl jsem si vysvětlit krok který mi nedošel. A možná, že to platí pro více studujících. Jinak pěkné. ...