Algoritmy řazení O(N logN) - Historie editací

109.72.14.213: /* Řazení haldou (heapsort) */

2016-06-04T07:30:07Z

Řazení haldou (heapsort)

← Starší verze		Verze z 4. 6. 2016, 07:30
Řádka 12:		Řádka 12:
	V kostce: na poli uděláme haldu a max prvky vyměňujeme s posledními prvky haldy a haldu obnovujeme.		V kostce: na poli uděláme haldu a max prvky vyměňujeme s posledními prvky haldy a haldu obnovujeme.

		+	Hezká vizualizace: http://varkor.com/mathematics/heapsort/?0,1,1,2,3,5,8,13,21,34,55,89,144,233

	== Shellovo řazení (shellsort) ==		== Shellovo řazení (shellsort) ==

Acolade: kategorizace

2014-02-20T06:36:50Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:36
Řádka 60:		Řádka 60:

	Radix sort =???		Radix sort =???
		+	[[Kategorie:fav-kiv-bzinf]]

Tester: /* Řazení dělením (splitsort, quicksort) */

2011-08-30T22:50:35Z

Řazení dělením (splitsort, quicksort)

← Starší verze		Verze z 30. 8. 2011, 22:50
Řádka 40:		Řádka 40:
	v každém podstromu vzájemně vyměníme větší a menší prvky než pivot.		v každém podstromu vzájemně vyměníme větší a menší prvky než pivot.

		+	Výukové videjko: http://www.youtube.com/watch?v=y_G9BkAm6B8

	== Řazení slucováním (mergesort) ==		== Řazení slucováním (mergesort) ==

Tester: /* Shellovo řazení (shellsort) */

2011-08-30T22:44:12Z

Shellovo řazení (shellsort)

← Starší verze		Verze z 30. 8. 2011, 22:44
Řádka 27:		Řádka 27:
	V kostce: rozdělení do stromu podle kroku (třeba na osminy), insertsort větví, a pak insertsort čtvrtin, polovin, konec		V kostce: rozdělení do stromu podle kroku (třeba na osminy), insertsort větví, a pak insertsort čtvrtin, polovin, konec

		+	Poměrně zajímavě udělaná ukázka z kartama: http://www.youtube.com/watch?v=QG8hs0wqmqk

	== Řazení dělením (splitsort, quicksort) ==		== Řazení dělením (splitsort, quicksort) ==

Tester: /* Řazení slucováním (mergesort) */

2011-08-30T22:39:12Z

Řazení slucováním (mergesort)

← Starší verze		Verze z 30. 8. 2011, 22:39
Řádka 52:		Řádka 52:
	2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme		2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme

		+	Bezva video - http://www.youtube.com/watch?v=GCae1WNvnZM

Tester v 10. 8. 2011, 09:28

2011-08-10T09:28:07Z

← Starší verze		Verze z 10. 8. 2011, 09:28
Řádka 46:		Řádka 46:
	a postupujeme až sloučíme obě poloviny původního pole. Je to nejčasteji používaná metoda a je stabilní.)		a postupujeme až sloučíme obě poloviny původního pole. Je to nejčasteji používaná metoda a je stabilní.)

−	V kostce: jako když mícháme karty - 2 balíčky a děláme	+	V kostce: jako když mícháme karty - 2 balíčky a děláme [[Soubor:Mergesort.jpg]]
	???????		???????

Tester v 9. 8. 2011, 18:05

2011-08-09T18:05:15Z

← Starší verze		Verze z 9. 8. 2011, 18:05
Řádka 1:		Řádka 1:
		+	// přidat ukázky
		+
	Společné pro všechny: Řadíme stromem.		Společné pro všechny: Řadíme stromem.

−	Řazení haldou (heapsort)	+	== Řazení haldou (heapsort) ==
−	Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, ~~tri~~, ~~ctyri~~ atd. prvky, až	+
−	máme na poli ~~vytvorenu~~ haldu. ~~Následne zameníme~~ nejvyšší prvek (vyjmeme ho) s posledním a obnovíme	+	Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, tři, čtyři atd. prvky, až
		+	máme na poli vytvořenu haldu. Následně zaměníme nejvyšší prvek (vyjmeme ho) s posledním a obnovíme
	vlastnost haldy na n−1 prvcích. Obnovení haldy je O(log n) a obnovujeme po každém výběru, tedy O(n log2n)		vlastnost haldy na n−1 prvcích. Obnovení haldy je O(log n) a obnovujeme po každém výběru, tedy O(n log2n)
−	To opakujeme až zbude jednoprvková halda a celé pole je ~~serazené~~. Nestabilní (složitost závisí na vstupních datech)	+	To opakujeme až zbude jednoprvková halda a celé pole je seřazené. Nestabilní (složitost závisí na vstupních datech).

−	V kostce: na poli uděláme haldu a max prvky vyměňujeme s posledními prvky haldy a haldu obnovujeme	+	V kostce: na poli uděláme haldu a max prvky vyměňujeme s posledními prvky haldy a haldu obnovujeme.

−	Shellovo řazení (shellsort)	+
−	Posloupnost rozdělíme na podposloupnosti s krokem h (každý h-tý počínaje prvním, ~~pocínaje~~ druhým až	+	== Shellovo řazení (shellsort) ==
−	~~pocínaje~~ h − 1-ním), které nezávisle seradíme vkládáním (insertsortem). Následne snižujeme hodnotu h a	+
		+	Posloupnost rozdělíme na podposloupnosti s krokem h (každý h-tý počínaje prvním, počínaje druhým až
		+	počínaje h − 1-ním), které nezávisle seradíme vkládáním (insertsortem). Následne snižujeme hodnotu h a
	provádíme totéž až do serazení s h = 1. Prvky daleko od své výsledné pozice se k ní dostanou v menším		provádíme totéž až do serazení s h = 1. Prvky daleko od své výsledné pozice se k ní dostanou v menším
−	~~poctu kroku~~, než u ~~obycejného~~ insertsortu. Shell - ~~pocátecní~~ h = polovina délky pole, snížení ~~vydelením~~	+	počtu kroků, než u obyčejného insertsortu.
−	~~dvema;~~ Knuth - posloupnost 3i + 1, ~~pocátecní~~ h = její prvek nejbližší ~~tretine~~ délky pole. Jednoduchý a	+
−	efektivní algoritmus, složitá analýza, nestabilní.	+	* Shell - počátecní h = polovina délky pole, snížení vydělením dvěma
		+	* Knuth - posloupnost 3i + 1, počáteční h = její prvek v nejbližší třetině délky pole
		+
		+	Jednoduchý a efektivní algoritmus, složitá analýza, nestabilní.

	V kostce: rozdělení do stromu podle kroku (třeba na osminy), insertsort větví, a pak insertsort čtvrtin, polovin, konec		V kostce: rozdělení do stromu podle kroku (třeba na osminy), insertsort větví, a pak insertsort čtvrtin, polovin, konec

−	~~Řazení dělením (splitsort, quicksort)~~
−	~~Urcíme prvek, jehož hodnota bude rozdelovat pole (pivot). Procházíme z obou stran pole a menší hodnoty~~
−	~~vpravo prohazujeme s vetšími vlevo, až se oba pruchody potkají. Na tuto pozici presuneme pivot - vlevo jsou~~
−	~~hodnoty menší, vpravo vetší. Totéž provedeme s cástí pole vlevo od pivotu i vpravo od nej. Rekurze koncí,~~
−	~~je-li predán pouze jeden prvek k serazení. Nejcasteji se pivot urcuje jako krajní prvek pole (nezasahuje pak~~
−	~~do procesu delení). Lze použít zásobník místo rekurze. Snadno implementovatelné, nestabilní.~~

−	~~Rozdělení~~ do stromu podle pivotů (prvek velikostně cca uprostřed podstromu, ideálně medián, ale může být i náhodný),	+	== Řazení dělením (splitsort, quicksort) ==
−	v každém podstromu vzájemně vyměníme větší a menší prvky než pivot	+
		+	Určíme prvek, jehož hodnota bude rozdělovat pole (pivot). Procházíme z obou stran pole a menší hodnoty
		+	vpravo prohazujeme s vetšími vlevo, až se oba průchody potkají. Na tuto pozici přesuneme pivot - vlevo jsou
		+	hodnoty menší, vpravo vetší. Totéž provedeme s částí pole vlevo od pivotu i vpravo od nej. Rekurze končí,
		+	je-li předán pouze jeden prvek k seřazení. Nejčasteji se pivot určuje jako krajní prvek pole (nezasahuje pak
		+	do procesu dělení). Lze použít zásobník místo rekurze. Snadno implementovatelné, nestabilní.
		+
		+	V kostce: rozdělení do stromu podle pivotů (prvek velikostně cca uprostřed podstromu, ideálně medián, ale může být i náhodný),
		+	v každém podstromu vzájemně vyměníme větší a menší prvky než pivot.
		+
		+
		+	== Řazení slucováním (mergesort) ==
		+
		+	Pole je rekurzivně rozdělováno na poloviny. Dojdeme až na úroveň dvojic prvku, které seřadíme (sloučíme).
		+	O úroven výše opět po dvojicích sloučíme (kopírujeme vždy menší prvek z obou polí a posuneme se za nej)
		+	a postupujeme až sloučíme obě poloviny původního pole. Je to nejčasteji používaná metoda a je stabilní.)
		+
		+	V kostce: jako když mícháme karty - 2 balíčky a děláme
		+	???????

−	~~Řazení slucováním (mergesort)~~	+	. Procházíme 2 podstromy a řadíme posunem
−	~~Pole je rekurzivne rozdelováno na poloviny. Dojdeme až na úroven dvojic prvku, které seradíme (sloucíme).~~	+
−	~~O úroven výše opet po dvojicích sloucíme (kopírujeme vždy menší prvek z obou polí a posuneme se za nej)~~	+
−	~~a postupujeme až sloucíme obe poloviny puvodního pole. Je to nejcasteji používaná metoda a je stabilní.)~~	+
−	~~V kostce: jako když mícháme karty - 2 balíčky a děláme~~ . Procházíme 2 podstromy a řadíme posunem	+
	2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme		2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme

Řádka 40:		Řádka 56:
	Nestabilní metody lze "zestabilnit" například zpřeházením dat na vstupu.		Nestabilní metody lze "zestabilnit" například zpřeházením dat na vstupu.

−	Radix sort	+	Radix sort =???

Tester: Založena nová stránka: Společné pro všechny: Řadíme stromem. Řazení haldou (heapsort) Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, tri, c...

2011-08-08T15:03:24Z

Založena nová stránka: Společné pro všechny: Řadíme stromem. Řazení haldou (heapsort) Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, tri, c...

Nová stránka

Společné pro všechny: Řadíme stromem.

Řazení haldou (heapsort)
Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, tri, ctyri atd. prvky, až
máme na poli vytvorenu haldu. Následne zameníme nejvyšší prvek (vyjmeme ho) s posledním a obnovíme
vlastnost haldy na n−1 prvcích. Obnovení haldy je O(log n) a obnovujeme po každém výběru, tedy O(n log2n)
To opakujeme až zbude jednoprvková halda a celé pole je serazené. Nestabilní (složitost závisí na vstupních datech)

V kostce: na poli uděláme haldu a max prvky vyměňujeme s posledními prvky haldy a haldu obnovujeme

Shellovo řazení (shellsort)
Posloupnost rozdělíme na podposloupnosti s krokem h (každý h-tý počínaje prvním, pocínaje druhým až
pocínaje h − 1-ním), které nezávisle seradíme vkládáním (insertsortem). Následne snižujeme hodnotu h a
provádíme totéž až do serazení s h = 1. Prvky daleko od své výsledné pozice se k ní dostanou v menším
poctu kroku, než u obycejného insertsortu. Shell - pocátecní h = polovina délky pole, snížení vydelením
dvema; Knuth - posloupnost 3i + 1, pocátecní h = její prvek nejbližší tretine délky pole. Jednoduchý a
efektivní algoritmus, složitá analýza, nestabilní.

V kostce: rozdělení do stromu podle kroku (třeba na osminy), insertsort větví, a pak insertsort čtvrtin, polovin, konec

Řazení dělením (splitsort, quicksort)
Urcíme prvek, jehož hodnota bude rozdelovat pole (pivot). Procházíme z obou stran pole a menší hodnoty
vpravo prohazujeme s vetšími vlevo, až se oba pruchody potkají. Na tuto pozici presuneme pivot - vlevo jsou
hodnoty menší, vpravo vetší. Totéž provedeme s cástí pole vlevo od pivotu i vpravo od nej. Rekurze koncí,
je-li predán pouze jeden prvek k serazení. Nejcasteji se pivot urcuje jako krajní prvek pole (nezasahuje pak
do procesu delení). Lze použít zásobník místo rekurze. Snadno implementovatelné, nestabilní.

Rozdělení do stromu podle pivotů (prvek velikostně cca uprostřed podstromu, ideálně medián, ale může být i náhodný),
v každém podstromu vzájemně vyměníme větší a menší prvky než pivot

Řazení slucováním (mergesort)
Pole je rekurzivne rozdelováno na poloviny. Dojdeme až na úroven dvojic prvku, které seradíme (sloucíme).
O úroven výše opet po dvojicích sloucíme (kopírujeme vždy menší prvek z obou polí a posuneme se za nej)
a postupujeme až sloucíme obe poloviny puvodního pole. Je to nejcasteji používaná metoda a je stabilní.)
V kostce: jako když mícháme karty - 2 balíčky a děláme . Procházíme 2 podstromy a řadíme posunem
2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme

Nestabilní metody lze "zestabilnit" například zpřeházením dat na vstupu.

Radix sort