Triedenie výberom - História úprav

Matúš Nečas: /* Pseudokód */

2021-04-19T16:50:39Z

Pseudokód

Matúš Nečas: /* Pseudokód */

2021-04-19T16:49:38Z

Pseudokód

Matúš Nečas: /* Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch */

2021-04-19T16:49:03Z

Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch

Matúš Nečas: /* Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch */

2021-04-19T16:10:57Z

Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch

Matúš Nečas: /* Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch */

2021-04-19T16:08:50Z

Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch

Filip Tomek: /* Heap Sort */

2021-04-19T15:56:06Z

Heap Sort

Matúš Nečas: /* Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch */

2021-04-19T15:55:04Z

Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch

Matúš Nečas: /* Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch */

2021-04-19T15:54:02Z

Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch

Filip Tomek: /* Algoritmus Heap Sort */

2021-04-19T15:51:50Z

Algoritmus Heap Sort

Filip Tomek: /* Algoritmus Heapify */

2021-04-19T15:45:40Z

Algoritmus Heapify

@@ Riadok 70: / Riadok 70: @@
 :2. Nech: <code>pravy = 2 * i + 2</code>
 :3. Nech: <code>max = i</code>
-:4. Je <code>lavy < dlzka</code> a zároveň <code>pole[max] > pole[i]</code> ?
+:4. Je <code>lavy < dlzka</code> a zároveň <code>pole[lavy] > pole[max]</code> ?
 ::: Ak áno:
 :::::4.1. Nech: <code>max = lavy</code>
 ::: Ak nie:
 :::::4.1. Pokračuj krokom 5.
-:5. Je <code>pravy < dlzka</code> a zároveň <code>pole[max] > pole[i]</code> ?
+:5. Je <code>pravy < dlzka</code> a zároveň <code>pole[pravy] > pole[max]</code> ?
 ::: Ak áno:
 :::::5.1. Nech: <code>max = pravy</code>

@@ Riadok 70: / Riadok 70: @@
 :2. Nech: <code>pravy = 2 * i + 2</code>
 :3. Nech: <code>max = i</code>
-:4. Je <code>lavy < dlzka</code> a zároveň <code>pole[lavy] > pole[i]</code> ?
+:4. Je <code>lavy < dlzka</code> a zároveň <code>pole[max] > pole[i]</code> ?
 ::: Ak áno:
 :::::4.1. Nech: <code>max = lavy</code>
 ::: Ak nie:
 :::::4.1. Pokračuj krokom 5.
-:5. Je <code>pravy < dlzka</code> a zároveň <code>pole[pravy] > pole[i]</code> ?
+:5. Je <code>pravy < dlzka</code> a zároveň <code>pole[max] > pole[i]</code> ?
 ::: Ak áno:
 :::::5.1. Nech: <code>max = pravy</code>

@@ Riadok 296: / Riadok 296: @@
 </tab>
-<tab name="Iterácia C++" block>
+<tab name="Iteračná C++" block>
 <syntaxhighlight lang="C++">
 #include <iostream>
@@ Riadok 462: / Riadok 462: @@
-<tab name="Iterácia Java" block>
+<tab name="Iteráčná Java" block>
 <syntaxhighlight lang="Java">
 class HeapSortIT {
@@ Riadok 543: / Riadok 543: @@
 </tab>
-<tab name="Rekurzia Java" block>
+<tab name="Rekurzívna Java" block>
 <syntaxhighlight lang="Java">
 class HeapSortRE {
@@ Riadok 619: / Riadok 619: @@
 </tab>
-<tab name="Iterácia Python3" block>
+<tab name="Iteračná Python3" block>
 <syntaxhighlight lang="Python3">
 def heapify(pole, n):
@@ Riadok 681: / Riadok 681: @@
 </tab>
-<tab name="Rekurzia Python3" block>
+<tab name="Rekurzívna Python3" block>
 <syntaxhighlight lang="Python3">
 def heapify(pole, n, i):

@@ Riadok 360: / Riadok 360: @@
              return;
+         }
+     }
+}

← Staršia verzia		Verzia zo dňa a času 16:08, 19. apríl 2021
Riadok 233:		Riadok 233:
	int main()		int main()
	{		{
−	int pole[]= {10, 5, 2, 9, 8, 7, 1, 3, 4, 0~~, -1~~, -1};	+	int pole[]= {10, 5, 2, 9, 8, 7, 1, 3, 4, 0, -1};
	int dlzka = sizeof(pole) / sizeof(pole[0]);		int dlzka = sizeof(pole) / sizeof(pole[0]);

Riadok 255:		Riadok 255:
	{		{

−	int lavy = 2 * index + 1;	+	int lavy = 2 * index + 1;
−	int pravy = 2 * index + 2;	+	int pravy = 2 * index + 2;
−	int max = index;	+	int max = index;

−	// určenie potomka s maximálnou hodnotou	+	// určenie potomka s maximálnou hodnotou
−	if(lavy < dlzka && pole[lavy] >= pole[~~pravy~~])	+	if(lavy < dlzka && pole[lavy] >= pole[max])
−	{	+	{
−	max = lavy;	+	max = lavy;
−	}	+	}

−	if(pravy < dlzka && pole[pravy] > pole[~~lavy~~])	+	if(pravy < dlzka && pole[pravy] > pole[max])
−	{	+	{
−	max = pravy;	+	max = pravy;
−	}	+	}

−	// porovnanie maximálneho potomka s rodičom	+	// porovnanie maximálneho potomka s rodičom
−	if(pole[max] > pole[index])	+	if(pole[max] > pole[index])
−	{	+	{
−	Vymen(&pole[max], &pole[index]);	+	Vymen(&pole[max], &pole[index]);
−	Heapify(pole, dlzka, max);	+	Heapify(pole, dlzka, max);
−	}	+	}
	}		}

@@ Riadok 21: / Riadok 21: @@
 ===Algoritmus Heapify===
-[[Súbor:Heapify.png|Vizualizácia algoritmu Heapify: Index i je iteračná premenná (pozri pseudokód). Ľavý a pravý potomok i-teho prvku je označený ako ĽP a PP. Prvky zafarbené na modro vyjadrujú pravú podhromadu i-teho prvku a prvky zafarbené na zeleno vyjadrujú ľavú podhromadu i-teho prvku. Chronlogický postup algoritmu je znázornený číslicami 1 až 3.|699px|náhľad|vpravo]]
+[[Súbor:Heapify.png|Vizualizácia algoritmu ''Heapify'': Index ''i'' je iteračná premenná (pozri pseudokód). Ľavý a pravý potomok i-teho prvku je označený ako ''ĽP'' a ''PP''. Prvky zafarbené na modro vyjadrujú pravú podhromadu i-teho prvku a prvky zafarbené na zeleno vyjadrujú ľavú podhromadu i-teho prvku. Chronlogický postup algoritmu je znázornený číslicami 1 až 3.|699px|náhľad|vpravo]]
 ''Heapify'' je kľúčovým podprogramom triediaceho algoritmu ''Heap Sort'', vďaka ktorému vieme efektíve zabezpečiť procedúry: vytvorenie hromady z poľa a zmazanie hromady.
@@ Riadok 96: / Riadok 96: @@
 * '''časová náročnosť:''' vždy linearitmická <math> O(n\log(n)) </math>, vďaka ktorej dokáže efektívne triediť veľmi veľké polia
-[[Súbor:HeapSort.png|Vizualizácia priebehu algoritmu Heap Sort: Algoritus je znázornený pomocou poľa, ktoré triedime a binárnej hromady, ktorú dané pole reprezentuje. Indexy i a j sú sú iteračné premenné (pozri pseudokód). Indexy ľavého a pravého potomka i-teho prvku sú označené ako ĽP a PP. Vrchol celej hromady je označený ako V. Prvky zafarbené na modro vyjadrujú pravú podhromadu i-teho prvku a prvky zafarbené na zeleno vyjadrujú ľavú pohromadu i-teho prvku. Nevyfarbené prvky vyjadrujú prvky, ktoré boli zmazané. Chronologický priebeh je označený číslicami 1 až 12. |500px|náhľad|vpravo]]
+[[Súbor:HeapSort.png|Vizualizácia priebehu algoritmu ''Heap Sort'': Algoritus je znázornený pomocou ''poľa'', ktoré triedime a binárnej hromady, ktorú dané pole reprezentuje. Indexy ''i'' a ''j'' sú sú iteračné premenné (pozri pseudokód). Indexy ľavého a pravého potomka i-teho prvku sú označené ako ''ĽP'' a ''PP''. Vrchol celej hromady je označený ako ''V''. Prvky zafarbené na modro vyjadrujú pravú podhromadu i-teho prvku a prvky zafarbené na zeleno vyjadrujú ľavú pohromadu i-teho prvku. Nevyfarbené prvky vyjadrujú prvky, ktoré boli zmazané. Chronologický priebeh je označený číslicami 1 až 12. |500px|náhľad|vpravo]]
 * '''priestorová náročnosť:''' konštantná <math>O(1)</math> pri iteračnej verzii, logaritmická <math>O(\log(n))</math> pri rekurzívnej verzii.

@@ Riadok 293: / Riadok 293: @@
+     }
+}
-</syntaxhighlight lang="C++">
+</syntaxhighlight>
 </tab>
 <tab name="Iterácia C++" block>
-<syntaxhighlight>
+<syntaxhighlight lang="C++">
 #include <iostream>

@@ Riadok 290: / Riadok 290: @@
+     {
          Vymen(&pole[0], &pole[j]);
          Heapify(pole, j, 0);
+     }
@@ Riadok 295: / Riadok 380: @@
 </syntaxhighlight>
 </tab>
 <tab name="Iterácia Java" block>

@@ Riadok 90: / Riadok 90: @@
 ===Algoritmus Heap Sort===
-Heapsort pri triedení vykonáva dve základné úlohy: Vytvorenie maximálnej binárnej hromady zo vstupného poľa a postupné mazanie jednotlivých prvkov z hromady. Pri oboch procedúrach využíva algoritmus Heapify.
+''Heap Sort'' pri triedení vykonáva dve základné úlohy: Vytvorenie maximálnej binárnej hromady zo vstupného poľa a postupné mazanie jednotlivých prvkov z hromady. Pri oboch procedúrach využíva algoritmus ''Heapify''.
 ====Vlastnosti algoritmu====
-* vhodný pre dátové štruktúry: pole
+* '''vhodný pre dátové štruktúry:''' pole
-* časová náročnosť: vždy linearitmická <math> O(n\log(n)) </math>, vďaka ktorej dokáže efektívne triediť veľmi veľké polia
+* '''časová náročnosť:''' vždy linearitmická <math> O(n\log(n)) </math>, vďaka ktorej dokáže efektívne triediť veľmi veľké polia
 [[Súbor:HeapSort.png|Vizualizácia priebehu algoritmu Heap Sort: Algoritus je znázornený pomocou poľa, ktoré triedime a binárnej hromady, ktorú dané pole reprezentuje. Indexy i a j sú sú iteračné premenné (pozri pseudokód). Indexy ľavého a pravého potomka i-teho prvku sú označené ako ĽP a PP. Vrchol celej hromady je označený ako V. Prvky zafarbené na modro vyjadrujú pravú podhromadu i-teho prvku a prvky zafarbené na zeleno vyjadrujú ľavú pohromadu i-teho prvku. Nevyfarbené prvky vyjadrujú prvky, ktoré boli zmazané. Chronologický priebeh je označený číslicami 1 až 12. |500px|náhľad|vpravo]]
-* priestorová náročnosť: konštantná <math>O(1)</math> pri iteračnej verzii, logaritmická <math>O(\log(n))</math> pri rekurzívnej verzii.
+* '''priestorová náročnosť:''' konštantná <math>O(1)</math> pri iteračnej verzii, logaritmická <math>O(\log(n))</math> pri rekurzívnej verzii.
-* druh triedenia: triedenie výberom (komparačný algoritmus)
+* '''druh triedenia:''' triedenie výberom (komparačný algoritmus)
-* stabilita triedenia: nestabilný
+* '''stabilita triedenia:''' nestabilný
-* miesto triedenia: vnútorné triedenie
+* '''miesto triedenia:''' vnútorné triedenie
 ====Základné časti algoritmu====
@@ Riadok 109: / Riadok 109: @@
 ====Slovný opis====
 =====Vytvorenie hromady=====
-Pri vytváraní hromady využijeme algoritmus Heapify, pričom hromadu vytvoríme spôsobom zospodu na vrch.
+Pri vytváraní hromady využijeme algoritmus ''Heapify'', pričom hromadu vytvoríme spôsobom zospodu na vrch.
-Najskôr si určíme rodiča posledného potomka. Využijeme rovnicu (3) z časti prehľad, ktorú si jemne upravíme:
+Najskôr si určíme rodiča posledného potomka. Využijeme rovnicu (3) z časti "Prehľad", ktorú si jemne upravíme:
   <center><math> \text{posledný rodič:} \ \  i = \left \lfloor \frac{\text{posledný index } - \ 1}{2}   \right \rfloor  = \left \lfloor\frac{\text{dĺžka } - \ 2}{2} \right \rfloor = \left \lfloor \frac{\text{dĺžka}}{2}\right \rfloor  - 1  </math></center>
-Následne zavoláme Heapify na podhromadu s vrcholom na indexe i. Potom postupne zmenšujeme index i o 1 a opakovane naňho voláme Heapify až do chvíle, kým neprídeme na začiatok poľa. Touto procedúrou preusporiadavame spodné jednoprvkové podhromady do 3-prvkových pohromád, tie do 7-prvkových podhromád ... až kým nedostaneme jednu N-prvkovú hromadu, kde N je počet prvkov v poli. Schematicky by sme to mohli napísať takto:
+Následne zavoláme ''Heapify'' na podhromadu s vrcholom na indexe ''i''. Potom postupne zmenšujeme index ''i'' o ''1'' a opakovane naňho voláme ''Heapify'' až do chvíle, kým neprídeme na začiatok poľa. Touto procedúrou preusporiadavame spodné jednoprvkové podhromady do 3-prvkových podhromád, tie do 7-prvkových podhromád ... až kým nedostaneme jednu N-prvkovú hromadu, kde ''N'' je počet prvkov v poli. Schematicky by sme to mohli napísať takto:
 <center><math> \text{pre } i \text{ z intervalu } \left \langle \left \lfloor \frac {\text{dĺžka}}{2} \right \rfloor - 1 \quad  ; \quad 0 \right \rangle :\  \text{Heapify( pole[],  dĺžka,  i )}</math></center>
 =====Zmazanie hromady=====
-Pri mazaní hromady vykonáme dve operácie. Ako prvé vymeníme  prvok na vrchu hromady s koncovým prvkom hromady. Prvok čo je na konci poľa považujeme už za zmazaný, preto veľkosť hromady znížime o 1. Ďalej, aby sme splnili podmienky pre maximálnu binárnu hromadu, zavoláme funkciu Heapify na celú hromadu (vrch hromady je 0-tý prvok v poli). Tento proces opakujeme, pokiaľ v hromade neostanú žiadne prvky.
+Pri mazaní hromady vykonáme dve operácie. Ako prvé vymeníme  prvok na vrchu hromady s koncovým prvkom hromady. Prvok čo je na konci poľa považujeme už za zmazaný, preto veľkosť hromady znížime o 1. Ďalej, aby sme splnili podmienky pre maximálnu binárnu hromadu, zavoláme funkciu ''Heapify'' na celú hromadu (vrch hromady je 0-tý prvok v poli). Tento proces opakujeme, pokým v hromade neostanú žiadne prvky.
 Poznámka: Pri triediacom algoritme nemusíme mazať celú hromadu, stačí nám, keď v hromade ostane jeden prvok, pretože vtedy bude vstupné pole už utriedené.
@@ Riadok 124: / Riadok 124: @@
 <center><math>\text{pre } j \text{ z intervalu } \left \langle \text{dĺžka - 1} \quad ; \quad 0 \right ) : \ \  \text{Vymeň(pole[0], pole[$j$])} \ \ a \ \ \text{Heapify(pole[], dĺžka, 0)} </math></center>
-Z hľadiska implementácie môžeme vytvoriť rekurzívnu aj iteračnú verziu, čo závisí len od toho, ako je implementovaná funkcia Heapify.
+Z hľadiska implementácie môžeme vytvoriť '''iteračnú''' aj '''rekurzívnu''' verziu, čo závisí len od toho, ako je implementovaná funkcia ''Heapify''.
 ====Pseudokód====
-Nech funkcia Heap Sort má nasledovný prototyp: <code>HeapSort(pole[], dlzka)</code>
+Nech funkcia ''Heap Sort'' má nasledovný prototyp: <code>HeapSort(pole[], dlzka)</code>
 :1. Nech: <code>i = dlzka / 2 - 1</code>, kde "/" predstavuje celočíslené delenie.

@@ Riadok 22: / Riadok 22: @@
 ===Algoritmus Heapify===
 [[Súbor:Heapify.png|Vizualizácia algoritmu Heapify: Index i je iteračná premenná (pozri pseudokód). Ľavý a pravý potomok i-teho prvku je označený ako ĽP a PP. Prvky zafarbené na modro vyjadrujú pravú podhromadu i-teho prvku a prvky zafarbené na zeleno vyjadrujú ľavú podhromadu i-teho prvku. Chronlogický postup algoritmu je znázornený číslicami 1 až 3.|699px|náhľad|vpravo]]
-Heapify je kľúčovým podprogramom triediaceho algoritmu Heap Sort, vďaka ktorému vieme efektíve zabezpečiť procedúry: vytvorenie hromady z poľa a zmazanie hromady.
+''Heapify'' je kľúčovým podprogramom triediaceho algoritmu ''Heap Sort'', vďaka ktorému vieme efektíve zabezpečiť procedúry: vytvorenie hromady z poľa a zmazanie hromady.
-Princíp algoritmu Heapify spočíva v tom, že ak máme i-ty prvok v poli (v kompletnom binárnom strome), ktorého potomkovia tvoria dve samostatné podhromady, potom tieto dve podhromady preusporiadame do jednej hromady, pričom i-ty prvok bude jej vrcholom.
+Princíp algoritmu ''Heapify'' spočíva v tom, že ak máme i-ty prvok v poli (v kompletnom binárnom strome), ktorého potomkovia tvoria dve samostatné podhromady, potom tieto dve podhromady preusporiadame do jednej hromady, pričom i-ty prvok bude jej vrcholom.
 ====Vlastnosti algoritmu====
-* dátová štruktúra: hromada (reprezentovaná ako: pole)
+* '''dátová štruktúra:''' hromada (reprezentovaná ako: pole)
-* časová zložitosť: lineárna <math>O(n)</math>
+* '''časová zložitosť:''' lineárna <math>O(n)</math>
-* priestorová zložitosť: konštantná <math>O(1)</math> pri iteračnej verzii, <math>O(log(n))</math> pri rekurzívnej verzii
+* '''priestorová zložitosť:''' konštantná <math>O(1)</math> pri iteračnej verzii, <math>O(log(n))</math> pri rekurzívnej verzii
 ====Základné časti algoritmu====
@@ Riadok 38: / Riadok 38: @@
 ====Slovný opis algoritmu====
-Na vstupe prijmeme pole a index i, v ktorom chceme vytvoriť hromadu (Max Heap). Musí byť splnená podmienka, že oba potomkovia i-teho prvku tvoria dve samostatné podhromady.
+Na vstupe prijmeme ''pole'' a index ''i'', v ktorom chceme vytvoriť hromadu (''Max Heap''). Musí byť splnená podmienka, že oba potomkovia i-teho prvku tvoria dve samostatné podhromady.
-Najskôr skontrolujeme, či prvok na indexe i má nejakých potomkov (využijeme rovnice (1) a (2) z časti "Prehľad"). Ak nemá žiadnych potomkov, funkcia skončí, pretože i predstavuje vrchol jednoprvkovej hromady. Ak má práve jedného potomka, tento potomok je zároveň aj jeho maximálnym potomkom. Ak má práve dvoch potomkov, tak porovnáme ich hodnoty a vyberieme z nich maximálneho potomka. Následne skontrolujeme veľkosť maximálneho potomka a jeho rodiča (prvok na indexe i). Ak je rodič väčší, funkcia skončí, pretože želaná hromada už je utvorená. Ak nie, vymeníme rodiča a maximálneho potomka. Ak nastala výmena, musíme skontrolovať ovplyvnenú podhromadu, tj. zopakovať tento sled krokov pre podhromadu, ktorej vrchol bude v maximálnom potomkovi i-teho prvku.
+Najskôr skontrolujeme, či ''prvok'' na indexe ''i'' má nejakých potomkov (využijeme rovnice (1) a (2) z časti "Prehľad"). Ak nemá žiadnych potomkov, funkcia skončí, pretože ''i'' predstavuje vrchol jednoprvkovej hromady. Ak má práve jedného potomka, tento potomok je zároveň aj jeho maximálnym potomkom. Ak má práve dvoch potomkov, tak porovnáme ich hodnoty a vyberieme z nich maximálneho potomka. Následne skontrolujeme veľkosť maximálneho potomka a jeho rodiča (prvok na indexe ''i''). Ak je rodič väčší, funkcia skončí, pretože želaná hromada už je utvorená. Ak nie, vymeníme rodiča a maximálneho potomka. Ak nastala výmena, musíme skontrolovať ovplyvnenú podhromadu, tj. zopakovať tento sled krokov pre podhromadu, ktorej vrchol bude v maximálnom potomkovi i-teho prvku.
-Z hľadiska implementácie môžeme vytvoriť iteračnú aj rekurzívnu verziu.
+Z hľadiska implementácie môžeme vytvoriť '''iteračnú''' aj '''rekurzívnu''' verziu.
 ====Pseudokód====