Řadící algoritmy - Historie editací

Spravce: /* Vlastnosti */ U složitostí používáme velké N

2014-12-11T16:31:36Z

Vlastnosti: U složitostí používáme velké N

← Starší verze		Verze z 11. 12. 2014, 16:31
Řádka 23:		Řádka 23:
	* Algoritmus provede řazení rychleji (v menším počtu kroků), pokud je vstupní posloupnost již částečně seřazená.		* Algoritmus provede řazení rychleji (v menším počtu kroků), pokud je vstupní posloupnost již částečně seřazená.
	<div class="Poznamka">Poznámky:		<div class="Poznamka">Poznámky:
−	# Mluvíme-li o zrychlení, myslíme tím zrychlení '''asymptotické'''.<br />''Tedy třeba to, že v „dobrých“ případech se dostaneme ze složitosti <tt>O(n<sup>2</sup>)</tt> na <tt>O(n)</tt> apod.''	+	# Mluvíme-li o zrychlení, myslíme tím zrychlení '''asymptotické'''.<br />''Tedy třeba to, že v „dobrých“ případech se dostaneme ze složitosti <tt>O(N<sup>2</sup>)</tt> na <tt>O(N)</tt> apod.''
	# Počet operací by měl klesat '''postupně''' s počtem a velikostí seřazených bloků ve vstupní posloupnosti.<br />''Pokud například k algoritmu, který není přirozený, pouze předřadíme test, zda už posloupnost náhodou není seřazená na vstupu, stále výsledný algoritmus nebudeme považovat za přirozený.''		# Počet operací by měl klesat '''postupně''' s počtem a velikostí seřazených bloků ve vstupní posloupnosti.<br />''Pokud například k algoritmu, který není přirozený, pouze předřadíme test, zda už posloupnost náhodou není seřazená na vstupu, stále výsledný algoritmus nebudeme považovat za přirozený.''
	</div>		</div>

Spravce: /* Vlastnosti */ Grafická úprava.

2014-12-11T16:30:20Z

Vlastnosti: Grafická úprava.

← Starší verze		Verze z 11. 12. 2014, 16:30
Řádka 15:		Řádka 15:
	== Vlastnosti ==		== Vlastnosti ==
	; Stabilita (''stable sorting'')		; Stabilita (''stable sorting'')
−	* ~~Pořadí~~ prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné)~~, zůstane zachované~~.	+	* Algoritmus vždy zachová pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné).
−	* Můžeme pak řadit podle více kritérií postupně.	+	<div class="Poznamka">
		+	U stabilních řadících algoritmů můžeme řadit podle více kritérií tak, že postupně aplikujeme řazení pomocí jednotlivých kritérií.
		+	</div>

	; Přirozenost (''natural, adaptive algorithm'')		; Přirozenost (''natural, adaptive algorithm'')
−	* ~~Pokud~~ je vstupní posloupnost již částečně seřazená~~, je řazení rychlejší~~.	+	* Algoritmus provede řazení rychleji (v menším počtu kroků), pokud je vstupní posloupnost již částečně seřazená.
−	* Myslí se tím zrychlení ''asymptotické''.	+	<div class="Poznamka">Poznámky:
−	*: Tedy třeba že v „dobrých“ případech se dostaneme ~~z ~~<tt>O(n<sup>2</sup>)</tt> na <tt>O(n)</tt> apod.	+	# Mluvíme-li o zrychlení, myslíme tím zrychlení '''asymptotické'''.<br />''Tedy třeba to, že v „dobrých“ případech se dostaneme ze složitosti <tt>O(n<sup>2</sup>)</tt> na <tt>O(n)</tt> apod.''
−	* Počet operací by měl klesat ''postupně'' s počtem a velikostí seřazených bloků ve vstupní posloupnosti ~~(s mírou seřazenosti~~ vstupu).	+	# Počet operací by měl klesat '''postupně''' s počtem a velikostí seřazených bloků ve vstupní posloupnosti.<br />''Pokud například k algoritmu, který není přirozený, pouze předřadíme test, zda už posloupnost náhodou není seřazená na vstupu, stále výsledný algoritmus nebudeme považovat za přirozený.''
		+	</div>

	== Známé algoritmy ==		== Známé algoritmy ==

Spravce: /* Vlastnosti */ Upřesnění pojmu Přirozený algoritmus

2014-12-11T10:40:17Z

Vlastnosti: Upřesnění pojmu Přirozený algoritmus

← Starší verze		Verze z 11. 12. 2014, 10:40
Řádka 14:		Řádka 14:

	== Vlastnosti ==		== Vlastnosti ==
−	; Stabilita (stable sorting)	+	; Stabilita (''stable sorting'')
	* Pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné), zůstane zachované.		* Pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné), zůstane zachované.
	* Můžeme pak řadit podle více kritérií postupně.		* Můžeme pak řadit podle více kritérií postupně.

−	; Přirozenost	+	; Přirozenost (''natural, adaptive algorithm'')
	* Pokud je vstupní posloupnost již částečně seřazená, je řazení rychlejší.		* Pokud je vstupní posloupnost již částečně seřazená, je řazení rychlejší.
		+	* Myslí se tím zrychlení ''asymptotické''.
		+	*: Tedy třeba že v „dobrých“ případech se dostaneme z <tt>O(n<sup>2</sup>)</tt> na <tt>O(n)</tt> apod.
		+	* Počet operací by měl klesat ''postupně'' s počtem a velikostí seřazených bloků ve vstupní posloupnosti (s mírou seřazenosti vstupu).

	== Známé algoritmy ==		== Známé algoritmy ==

Spravce: Oprava odkazu

2014-12-09T10:32:31Z

Oprava odkazu

← Starší verze		Verze z 9. 12. 2014, 10:32
Řádka 10:		Řádka 10:
	Pokud ale opravdu potřebujete jen něco seřadit, použijte knihovny vašeho prog. jazyka! Například v Javě:		Pokud ale opravdu potřebujete jen něco seřadit, použijte knihovny vašeho prog. jazyka! Například v Javě:
	Collection.sort(seznam);		Collection.sort(seznam);
−	Viz také: [[Java: Řazení ~~a vyhledávání~~]].	+	Viz také: [[Java: Řazení]].
	</div>		</div>

Řádka 36:		Řádka 36:

	== Související stránky ==		== Související stránky ==
−	* [[Java: Řazení ~~a vyhledávání~~]]	+	* [[Java: Řazení]]

	== Zdroje ==		== Zdroje ==
	* Mnohem více informací získáte na:[http://www.algoritmy.net/article/75/Porovnani-algoritmu Algoritmy.net → Porovnání algoritmů]		* Mnohem více informací získáte na:[http://www.algoritmy.net/article/75/Porovnani-algoritmu Algoritmy.net → Porovnání algoritmů]

Spravce: Přidán odkaz na Java: Řazení a vyhledávání

2014-12-09T10:06:37Z

Přidán odkaz na Java: Řazení a vyhledávání

← Starší verze		Verze z 9. 12. 2014, 10:06
Řádka 10:		Řádka 10:
	Pokud ale opravdu potřebujete jen něco seřadit, použijte knihovny vašeho prog. jazyka! Například v Javě:		Pokud ale opravdu potřebujete jen něco seřadit, použijte knihovny vašeho prog. jazyka! Například v Javě:
	Collection.sort(seznam);		Collection.sort(seznam);
		+	Viz také: [[Java: Řazení a vyhledávání]].
	</div>		</div>

Řádka 33:		Řádka 34:
	** Spojuje dílčí seřazené posloupnosti do delších.		** Spojuje dílčí seřazené posloupnosti do delších.
	** „Opačný postup“ než u Quick-sortu (od spodu nahoru).		** „Opačný postup“ než u Quick-sortu (od spodu nahoru).
		+
		+	== Související stránky ==
		+	* [[Java: Řazení a vyhledávání]]

	== Zdroje ==		== Zdroje ==
	* Mnohem více informací získáte na:[http://www.algoritmy.net/article/75/Porovnani-algoritmu Algoritmy.net → Porovnání algoritmů]		* Mnohem více informací získáte na:[http://www.algoritmy.net/article/75/Porovnani-algoritmu Algoritmy.net → Porovnání algoritmů]

Spravce: Přidána poznámka, že existuje Collection.sort(...)

2013-11-18T09:35:14Z

Přidána poznámka, že existuje Collection.sort(...)

← Starší verze		Verze z 18. 11. 2013, 09:35
Řádka 1:		Řádka 1:
	[[Category:VSE]][[Category:Informatika]][[Category:Programování]][[Category:Algoritmizace]]		[[Category:VSE]][[Category:Informatika]][[Category:Programování]][[Category:Algoritmizace]]
		+
		+	<div class="Poznamka">
		+	Řadicí algoritmy jsou hezkou a tradiční ukázkou jednoduchých algoritmů. Učíme se je, abychom:
		+	* si pocvičili práci s kolekcemi, podmínky a cykly,
		+	* prakticky si ukázali složitost a vlastnosti algoritmů,
		+	* uvědomili si, že je třeba vybírat vhodný algoritmus pro danou úlohu.
		+	</div>
		+	<div class="Varovani">
		+	Pokud ale opravdu potřebujete jen něco seřadit, použijte knihovny vašeho prog. jazyka! Například v Javě:
		+	Collection.sort(seznam);
		+	</div>

	== Vlastnosti ==		== Vlastnosti ==

Spravce: Vytvoření stránky

2013-10-31T12:31:09Z

Vytvoření stránky

Nová stránka

[[Category:VSE]][[Category:Informatika]][[Category:Programování]][[Category:Algoritmizace]]

== Vlastnosti ==
; Stabilita (stable sorting)
* Pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné), zůstane zachované.
* Můžeme pak řadit podle více kritérií postupně.

; Přirozenost
* Pokud je vstupní posloupnost již částečně seřazená, je řazení rychlejší.

== Známé algoritmy ==
* Insertion-sort
** Začínáme od prvního prvku, který tvoří „jednoprvkovou seřazenou posloupnost“.
** Postupně bereme další prvky a v každém kroku jeden prvek vložíme do seřazené posloupnosti, která se tak prodlouží.
* Shell-sort
** Simulace vyhledávacího stromu v poli
* Quick-sort
** Vybere „pivot“ („prostřední prvek“)
** Rozdělí prvky na ty, co jsou menší, a na ty, co jsou větší než pivot.
** Pak postupuje stejně v levé a pravé části.
* Merge-sort
** Spojuje dílčí seřazené posloupnosti do delších.
** „Opačný postup“ než u Quick-sortu (od spodu nahoru).

== Zdroje ==
* Mnohem více informací získáte na:[http://www.algoritmy.net/article/75/Porovnani-algoritmu Algoritmy.net → Porovnání algoritmů]