Sekvenční třídění, porovnávací algoritmy

Vše co se týká bakalářských státních závěrečných zkoušek.
ps
Matfyz(ák|ačka) level III
Příspěvky: 137
Registrován: 1. 6. 2006 08:47
Typ studia: Informatika Mgr.
Bydliště: Praha 4
Kontaktovat uživatele:

Sekvenční třídění, porovnávací algoritmy

Příspěvek od ps »

Nevíte někdo, co přesně se schovává pod touto bakalářskou otázkou Sekvenční třídění, porovnávací algoritmy? Já si nejsem úplně jist, co chtěl básník říci tím "sekvenční". Které třídící algoritmy pod to spadají a které ne?
Uživatelský avatar
beaver
Matfyz(ák|ačka) level III
Příspěvky: 189
Registrován: 2. 2. 2007 09:33
Typ studia: Nestuduji ale učím na MFF
Bydliště: Praha

Příspěvek od beaver »

Tak take nevim, co presne by to melo znamenat, ale moje predstava je, ze by clovek mel ke statnici umet nekolik tridicich algoritmu zalozenych na porovnavani a to jak internich, tak externich (tj. SelectSort, InsertSort, BubbleSort, HeapSort, QuickSort a MergeSort pro vnitrni a nasledne N-cestne a polyfazove trideni pro vnejsi).
To by podle meho nazoru melo stacit (k tomuto tematu). :wink:
Cožpak většina z nás svým způsobem nehledá svou kravičku?
T. Pratchett, z knihy "Kdepak je má kravička"
krystof
Matfyz(ák|ačka) level III
Příspěvky: 186
Registrován: 18. 1. 2005 15:15
Typ studia: Informatika Mgr.
Bydliště: Brno / 17. Listopad
Kontaktovat uživatele:

Příspěvek od krystof »

imo sekvencni jsou ty, kde se prohazovani provani postupne (quick, heap, merge), a v opozici k nim jsou paralelni, kde se prohazuje vic prvku zaroven - bitonicky trideni (takovy ty komparatorovy site, pokud si vzpominam, tak to bylo v ADS s Kucerou)
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

Ta "věta" zní:
Sekvenční třídění, porovnávací algoritmy, přihrádkové třídění, třídící sítě.
a já to chápu takto:
  1. porovnávací alg. - heap, quick, bubble, insert, ...
  2. přihrádkové třídění - bucket, counting, redix sort (http://hippies.matfyz.info/poznamky/pre ... y.php?ID=2)
  3. třídící sítě - např. to bitonické (http://hippies.matfyz.info/poznamky/pre ... .php?ID=23)
  4. sekvenční třídění - tudíž předpokládám je něco jiného, dle mého názoru to znamená, že třídí data sekvenčně, tj. jak mu přijdou do ruky, tedy např. merge sort
Dobrej přehled je třeba tady: http://agents.felk.cvut.cz/teaching/x33 ... oritmy.pdf
ps
Matfyz(ák|ačka) level III
Příspěvky: 137
Registrován: 1. 6. 2006 08:47
Typ studia: Informatika Mgr.
Bydliště: Praha 4
Kontaktovat uživatele:

Příspěvek od ps »

hippies píše:Ta "věta" zní:
Sekvenční třídění, porovnávací algoritmy, přihrádkové třídění, třídící sítě.
Takhle ta věta u oboru SPS právě že nezní, proto přemýšlím, co tam patří a co ne :-)
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

to je jedno, každopádně sekvenční třídění je prostě merge;)
Uživatelský avatar
joshis
Matfyz(ák|ačka) level III
Příspěvky: 127
Registrován: 23. 11. 2006 01:47
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od joshis »

Na zaklade meho nazoru a polozeni dotazu Googlu ("Sequential sorting") je skoro jasne, ze pravdu v tomto ne moc zavaznem sporu ma spis Krystof.

http://lankewicz.sewanee.edu/lankewicz/ ... lass6.html

"sekvenční třídění - tudíž předpokládám je něco jiného, dle mého názoru to znamená, že třídí data sekvenčně, tj. jak mu přijdou do ruky, tedy např. merge sort"

No, ja hlavne nevim co zde znamena "jak mu prijdou do ruky", merge sort je rozdel/panuj algoritmus, operace Merge je jen jednou casti.

Merge-sort zajiste je sekvencni, ale Quick-Sort data taky tridi "jak mu to prijde do ruky" a BubbleSort rovnez... Merge-sort je btw i porovnavaci algoritmus (pouziva porovnani pri slevani).

Navic ciste terminologicky mam pocit, ze to slovo "sekvencni" pasuje na tyto tridici algoritmy (QuickS, BubbleS, InsertionS, SelectionS, ...)...

Spis je me zajima, jestli je randomizovany QuickSort take sekvencni...(???)
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

Myslím, že sekvenční třídění jsou ta, která dovedou setřídit data se sekvenčním přístupem. Na to je nejlepší merge, já vim, že třeba Qsort na tom taky uděláš, ale není to ono.
Odpovědět

Zpět na „Bakalářské SZZ“