Juraj na 20:17, 16. august 2010

2010-08-16T20:17:18Z

Juraj na 20:12, 7. marec 2010

2010-03-07T20:12:06Z

Juraj na 19:18, 7. marec 2010

2010-03-07T19:18:35Z

Zobraziť rozdiely

Juraj na 21:09, 5. marec 2010

2010-03-05T21:09:05Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} TOC ==Insert sort== ==Shell sort==“

2010-02-03T21:06:18Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} __TOC__ ==Insert sort== ==Shell sort==“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie}}
__TOC__

==Insert sort==

==Shell sort==

@@ Riadok 111: / Riadok 111: @@
 Voľba vhodnej postupnosti skracovania kroku:
 *Pri použití Shellovej postupnosti (začína na polovičnej veľkosti poľa a zakaždým sa delí 2) je to <math>O(n^2)</math>.
-*Hibbardova postupnosť: (2k - 1) má časovú zložitosť <math>O(n^{3/2})</math>.
+*Hibbardova postupnosť: <math>(2^k - 1)</math> má časovú zložitosť <math>O(n^{3/2})</math>.
-*Sedgewickove postupnosti: (9(4i) - 9(2i) + 1) alebo (4i + 1 + 3(2i) + 1 ) majú časovú zložitosť <math>O(n^{4/3})</math>.
+*Sedgewickove postupnosti: <math>9\times4^i - 9\times2^i + 1</math> alebo <math>4^{i} - 3\times2^i + 1</math> majú časovú zložitosť <math>O(n^{4/3})</math>.
 *Existujú aj postupnosti dosahujúce zložitosť <math>O(n.log^{2}n)</math>, ale existencia postupnosti, ktorá prináša v najhoršom prípade časovú zložitosť <math>O(n log n)</math> zostáva otázna.
 ===Vzorový príklad===
 Začíname s neusporiadaným poľom (tabuľka 2). Porovnávame prvok na pozícii i s prvkom na pozícii i+krok.

← Staršia verzia		Verzia zo dňa a času 21:09, 5. marec 2010
Riadok 8:		Riadok 8:

	==Insert sort==		==Insert sort==
		+	Insert Sort nepatrí medzi výhodné algoritmy triedenia, nakoľko pracuje s operačnou zložitosťou O(n^2). Výsledkom jeho triedenia je stabilné pole (čiže zachová relatívne usporiadanie duplicitných kľúčov triedených prvkov). Insert Sort sa vyznačuje taktiež jednoduchou realizáciou a vhodný je hlavne na takmer usporiadané pole s malým počtom prvkov(pod 2 000). Pri usporadúvaní už usporiadaného poľa je Insert Sort dokonca rýchlejší ako Quicksort, pretože každý nový prvok porovnáva len s posledným v danom poli.
		+	===Princíp algorimtu===
		+	Princíp algoritmu Instert sort sa dá ľahko vysvetliť na princípe zotriedenia hráčskych kariet. Keď dostane hráč karty, snaží sa ich usporiadať podľa ich hodnoty jednoducho tak, že zoberie prvú kartu, ktorá netvorí žiadanú postupnosť a vloží ju na správne miesto. Samotný algoritmus, kde usporiadavame pole celých čísel od najmenšieho po najväčšie môžeme definovať ako:
		+	#rozdeľ triedené pole na zotriedenú a nezotriedenú časť. Na začiatku bude zotriedená časť prázdna a nezotriedená časť bude obsahovať všetky prvky. Začíname s prvkom na indexe i=0.
		+	#Zober prvok na indexe i z nezotriedenej časti a vlož ho na správne miesto v zotriedenej časti nasledovne:
		+	##Prvok, pre ktorý hľadáme správne umiestnenie si označme x. Index posledného prvku v zotriedenej časti označme ''j''.
		+	##Porovnaj prvok x, s prvkom z zotriedenej časti (pole[j]).
		+	##Ak je x < pole[j] , posuň tento prvok o jednu pozíciu doprava. Zmenši hodnotu j o 1 (posuň sa o jednu pozíciu doľava). Choď na krok 2.2
		+	##Ak je x > pole[j] , tak na pozíciu j vlož prvok x.
		+	##Opakuj algoritmus od začiatku (krok 2) s ďalším prvkom v nezotriedenej čast (i=i+1)

		+	===Vzorový príklad===
		+	Majme nezotriedené pole celých čísel (tabuľka 1, riadok č. 1). Jednotlivé riadky tabuľky reprezentujú iterácie triedenia. Čísla hrubo vytlačené znamenajú pozíciu prvku s ktorým v ďalšom kroku porovnávame susedný (ľavý) prvok. Červené písmo znamená aktuálnu zámenu dvoch prvkov. Zelené pozadie majú už usporiadané prvky, ktoré už nemusíme kontrolovať, či sú na správnej pozícii.
		+
		+	{\| border="1" cellpadding="3" cellspacing="0" class=wikitable
		+	\|+ Tabuľka 1 - Bubble sort
		+	\|-
		+	!iterácia
		+	!p[0]
		+	!p[1]
		+	!p[2]
		+	!p[3]
		+	!p[4]
		+	!p[5]
		+	!operácia
		+	\|-
		+	\|1.\|\|'''5'''\|\|3\|\|1\|\|2\|\|7\|\|4\|\|.
		+	\|-
		+	\|2.\|\|style="background-color:lightgreen"\|5\|\|'''3'''\|\|1\|\|2\|\|7\|\|4\|\|.
		+	\|-
		+	\|3.\|\|style="background-color:lightgreen;color:red"\|3\|\|style="background-color:lightgreen;color:red"\|5\|\|'''1'''\|\|2\|\|7\|\|4\|\|.
		+	\|-
		+	\|4.\|\|style="background-color:lightgreen"\|3\|\|style="background-color:lightgreen;color:red"\|'''1'''\|\|style="color:red"\|5\|\|2\|\|7\|\|4\|\|.
		+	\|-
		+	\|5.\|\|style="background-color:lightgreen;color:red"\|'''1'''\|\|style="background-color:lightgreen;color:red"\|3\|\|style="background-color:lightgreen"\|5\|\|'''2'''\|\|7\|\|4\|\|.
		+	\|-
		+	\|6.\|\|style="background-color:lightgreen"\|1\|\|style="background-color:lightgreen"\|3\|\|style="background-color:lightgreen;color:red"\|'''2'''\|\|style=";color:red"\|5\|\|7\|\|4\|\|.
		+	\|-
		+	\|7.\|\|style="background-color:lightgreen"\|1\|\|style="background-color:lightgreen;color:red"\|'''2'''\|\|style="background-color:lightgreen;color:red"\|3\|\|5\|\|7\|\|4\|\|.
		+	\|-
		+	\|8.\|\|style="background-color:lightgreen"\|1\|\|style="background-color:lightgreen"\|2\|\|style="background-color:lightgreen"\|3\|\|style="background-color:lightgreen"\|5\|\|'''7'''\|\|4\|\|.
		+	\|-
		+	\|9.\|\|style="background-color:lightgreen"\|1\|\|style="background-color:lightgreen"\|2\|\|style="background-color:lightgreen"\|3\|\|style="background-color:lightgreen"\|5\|\|style="background-color:lightgreen"\|7\|\|'''4'''\|\|.
		+	\|-
		+	\|10.\|\|style="background-color:lightgreen"\|1\|\|style="background-color:lightgreen"\|2\|\|style="background-color:lightgreen"\|3\|\|style="background-color:lightgreen"\|5\|\|style="background-color:lightgreen;color:red"\|'''4'''\|\|style="color:red"\|7\|\|.
		+	\|-
		+	\|11.\|\|style="background-color:lightgreen"\|1\|\|style="background-color:lightgreen"\|2\|\|style="background-color:lightgreen"\|3\|\|style="background-color:lightgreen;color:red"\|'''4'''\|\|style="background-color:lightgreen;color:red"\|5\|\|7\|\|.
		+	\|-
		+	\|12.\|\|style="background-color:lightgreen"\|1\|\|style="background-color:lightgreen"\|2\|\|style="background-color:lightgreen"\|3\|\|style="background-color:lightgreen"\|4\|\|style="background-color:lightgreen"\|5\|\|style="background-color:lightgreen"\|7\|\|.
		+	\|}
		+	===Implementácia algoritmu===
		+	====Insert Sort v pseudokóde <ref>Insertion sort - http://en.wikipedia.org/wiki/Insertion_sort</ref>====
		+	<source lang="delphi" line>
		+	insertionSort(array A)
		+	begin
		+	for i := 1 to length[A]-1 do
		+	begin
		+	value := A[i];
		+	j := i - 1;
		+	done := false;
		+	repeat
		+	if A[j] > value then
		+	begin
		+	A[j + 1] := A[j];
		+	j := j - 1;
		+	if j < 0 then
		+	done := true;
		+	end
		+	else
		+	done := true;
		+	until done;
		+	A[j + 1] := value;
		+	end;
		+	end;
		+	</source>
		+	====Insert Sort v C====
		+	<source lang="c" line>
		+	void InsertSort(int pole[ ], int pocet)
		+	{ int i,j,tmp;
		+	for(i=1; i<pocet; i++) // cez pole prejdeme pocet krat
		+	{ j=i; // 0..i-1 su uz zotriedene
		+	tmp=pole[j]; // tento prvok budeme zoradovat
		+	while( (j>0) && (pole[j-1] > tmp) ) // hladame, kde
		+	{ pole[j]=pole[j-1]; // prvok vlozime
		+	j--;
		+	}
		+	pole[j]=tmp; // vlozime prvok na spravne miesto
		+	}
		+	}
		+	</source>
	==Shell sort==		==Shell sort==
		+	===Princíp algorimtu===
		+	===Implementácia algoritmu===
		+
		+	=Zdroje a odkazy=
		+	<references/>

@@ Riadok 1: / Riadok 1: @@
-[[Kategória:Študijné materiály]]
+[[Kategória:Algoritmy triedenia]]
 {{Draft}}
 {{Skripta programovanie}}

Triedenie vkladaním - História úprav

Juraj na 20:17, 16. august 2010

Juraj na 20:12, 7. marec 2010

Juraj na 19:18, 7. marec 2010

Juraj na 21:09, 5. marec 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} __TOC__ ==Insert sort== ==Shell sort==“

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} TOC ==Insert sort== ==Shell sort==“