Diskusia – Quick sort

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre

Posledné komentáre sú na spodnej časti poslednej stránky.

Patrik Pastor

Člen

Patrik Pastor:21.4.2019 14:28

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

Odpovedať

David Hartinger

Vlastník

David Hartinger:21.4.2019 15:09

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.

Odpovedať

New kid back on the block with a R.I.P

Patrik Pastor

Člen

Patrik Pastor:21.4.2019 21:14

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

Odpovedať

Patrik Valkovič

Člen

Patrik Valkovič:21.4.2019 21:39

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.

Odpovedať

Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.

Patrik Pastor

Člen

Patrik Pastor:21.4.2019 21:48

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

Odpovedať

David Hartinger

Vlastník

David Hartinger:22.4.2019 12:33

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

Editované

Odpovedať

New kid back on the block with a R.I.P

Patrik Valkovič

Člen

Patrik Valkovič:22.4.2019 13:43

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]

Odpovedať

Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.

Andrej Ceperko

Člen

Andrej Ceperko:20.1.2022 21:17

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)

???

Odpovedať

Guri Lucie Vlčková

Člen

Guri Lucie Vlčková:8.2.2023 22:47

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

Editované

Odpovedať

Luboš Vidner

Člen

Luboš Vidner:16.4.2023 15:32

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é. ...

Odpovedať

Posledné komentáre sú na spodnej časti poslednej stránky.

Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 10 správy z 20.

Najčastejšie vyhľadávané

Diskusia – Quick sort