SZZ
»
temata
»
27-vyhledavani-razeni
»
razeni1
Historie:
•
razeni1
Starší verze
Správa médií
Poslední úpravy
Index
Přihlásit se
OBSAH WEBU
otazky
pravidla
tag
temata
wiki
about
poznamky
sidebar
ČTĚTE!
pravidla
návrhy
o webu
Obsah
27e - Řazení - algoritmy 1
Selection sort:
Bubble sort:
Heap sort:
Insertion sort:
Bubble - insert sort:
27e - Řazení - algoritmy 1
Selection sort:
řazení na princípe výberu
nestabilná
kvadratická zložitosť
video:
http://www.youtube.com/watch?v=TW3_7cD9L1A
Bubble sort:
princíp rovnaký ako v selection sort, ale metóda výberu extrému je iná
porovnáva prvky vedľa seba
modifikácie:
indikátor ukončenia
index prvej výmeny
shaker sort (z oboch strán striedavo)
shuttle sort - keď prišlo k výmene tak ten prvok posúval až kým sa nedostal na svoje miesto a potom pokračoval
najmenej efektívna metóda
najrýchlejšia metóda pre řazení už zoradeného poľa
najhorší prípad - najmenší prvok úplne na konci (môže sa presunúť vždy len o jedno miesto)
stabilná
prirodzená
kvadratická časová zložitosť
video:
http://www.youtube.com/watch?v=UnK5ueUgc88
Heap sort:
štruktúra stromového typu
platí, že medzi otcovským uzlom a všetkými synovskými uzlami platí rovnaká relácia usporiadania
Rekonštrukcia hromady:
po porušení pravidla hromady v niektorom uzle (najvýznamnejšie je pri porušení v koreni)
Sift (preosiatie)
logaritmická zložitosť
postupne „utriasanie“, začínajúc najspodnejším a najpravejším podstromom (koreň a aspoň jeden syn)
nestabilná
nechová sa prirodzene
linearitmická zložitosť
video:
http://www.youtube.com/watch?v=WYII2Oau_VY
přidávám ještě toto video:
http://www.youtube.com/watch?v=GnnmnQUudsU
- je to sice španělsky, ale je to tam je pěkně pomalu řešeno
Insertion sort:
pole je rozdelené na 2 časti - už zoradená a ešte nezoradená
nájdem kam ďalší prvok patrí, posuniem prvky, ktoré sú napravo od neho, vložím prvok
stabilita závisí na spôsobe vyhľadávania miesta pre vkladaný prvok
kvadratická zložitosť
video:
http://www.youtube.com/watch?v=Fr0SmtN0IJM
Bubble - insert sort:
kombinuje vyhľadanie miesta pre vkladanie a posun segmentu poľa v jednom cykle porovnávaním dvojíc prvkov
zarážka
stabilná
prirodzená
pracuje in situ
kvadratická zložitosť
temata/27-vyhledavani-razeni/razeni1.txt · Poslední úprava: 2011/06/06 18:52 autor: vagabund
Starší verze
Zpětné odkazy
Nahoru