Stránka sa načítava, prosím čakajte…
© 2005 – 2024 Roman Horváth, všetky práva vyhradené. Dnes je 3. 5. 2024.
Dátum: 4. 4. 2017, pred niekoľkými rokmi
Verzia v Pascale.
~
program bublinkove_triedenie; uses crt; const dlzka = 10; var pole: array [1 .. dlzka] of integer; i, j, koniec, novyKoniec: integer; procedure vymen(i, j: integer); var c: integer; begin c := pole[i]; pole[i] := pole[j]; pole[j] := c end; procedure vypis_pole; var i: integer; begin write(pole[1]:2); for i := 2 to dlzka do write(' ', pole[i]:2); writeln end; begin clrscr; randomize; for i := 1 to dlzka do begin write('Zadaj prvok ', i, ': '); { readln(pole[i]) } pole[i] := -5 + random(25); writeln(pole[i]) end; writeln; vypis_pole; writeln; { Pred optimalizáciou } for i := dlzka - 1 downto 2 do begin for j := 1 to i do if pole[j] > pole[j + 1] then vymen(j, j + 1); vypis_pole end; writeln; for i := 1 to dlzka do begin write('Zadaj prvok ', i, ': '); { readln(pole[i]) } pole[i] := -5 + random(25); writeln(pole[i]) end; writeln; vypis_pole; writeln; { Po optimalizácii } koniec := dlzka - 1; repeat novyKoniec := 0; for i := 1 to koniec do if pole[i] > pole[i + 1] then begin vymen(i, i + 1); novyKoniec := i end; koniec := novyKoniec; vypis_pole until koniec = 0; readln end.
Verzia v Jave pracujúca s verziou frameworku GRobot 1.75 (na sfunkčnenie s nižšími verziami treba zdrojový kód upraviť; s vyššími verziami sfunkčnenie programu môže/nemusí vyžadovať zásahy)…
~
import knižnica.GRobot; import static knižnica.GRobot.Svet.*; public class BubbleSort extends GRobot { private Zoznam<Integer> zoznam = new Zoznam<Integer>(); private int pole[]; private void vymeň(int i, int j) { int c = pole[i]; pole[i] = pole[j]; pole[j] = c; } private BubbleSort() { // Verzia so zoznamom for (int i = 0; i < 10; ++i) zoznam.pridaj((int)náhodnéCeléČíslo(-5, 20)); vypíšRiadok(zoznam, riadok); // Pred optimalizáciou // V tomto komentári vysvetlíme dôvody nášho spôsobu zostavenia // cyklov for. Najskôr uvedieme nesprávny zápis cyklov: // // for (int i = 0; i < zoznam.veľkosť() - 1; ++i) // { // for (int j = 0; j < zoznam.veľkosť() - 1 - i; ++j) // // Tento spôsob je nesprávny, pretože (v programovacom jazyku Java // a podobných) by sa pri každej iterácii museli vykonať zbytočné // výpočty (vo vonkajšom cykle by to bolo „zoznam.veľkosť() - 1“ // a vo vnútornom „zoznam.veľkosť() - 1 - i“), ktoré mali slúžiť // na overenie ukončenia obidvoch cyklov for (to jest na určenie // „horných hraníc“ cyklov). // // Správnejší zápis cyklov (nižšie) potrebujeme „menej“ výpočtov // (myslené mierne ironicky, pretože v skutočnosti potrebuje len // jeden). Pri tomto zápise cyklov totiž hodnota riadiacej // premennej i priamo určuje „hornú hranicu“ (inak povedané // podmienku ukončenia cyklu) riadiacej premennej j, takže nie // sú potrebné žiadne nadbytočné výpočty. // Výpočet zoznam.veľkosť() - 1 sa vykoná len raz – ním sa // štartuje vonkajší cyklus for. Hodnota i klesá do 1, // pretože nemá zmysel, aby i malo nižšiu hodnotu než 1. // (Dôvod: Pozrime sa na podmienku vnútorného cyklu: j < i. // Hodnota j sa začína na nule a nula nie je menšia než nula, // preto najmenšia zmysluplná hodnota i je 1.) for (int i = zoznam.veľkosť() - 1; i > 0; --i) { for (int j = 0; j < i; ++j) if (zoznam.daj(j) > zoznam.daj(j + 1)) zoznam.vymeň(j, j + 1); vypíšRiadok(zoznam); } vypíšRiadok(); zoznam.vymaž(); for (int i = 0; i < 10; ++i) zoznam.pridaj((int)náhodnéCeléČíslo(-5, 20)); vypíšRiadok(zoznam, riadok); // Po optimalizácii { int koniec = zoznam.veľkosť() - 1; do { int novýKoniec = 0; for (int i = 0; i < koniec; ++i) { if (zoznam.daj(i) > zoznam.daj(i + 1)) { zoznam.vymeň(i, i + 1); novýKoniec = i; } } koniec = novýKoniec; vypíšRiadok(zoznam); } while (koniec != 0); } vypíšRiadok(); // Verzia s poľom pole = new int[10]; for (int i = 0; i < pole.length; ++i) pole[i] = (int)náhodnéCeléČíslo(-5, 20); vypíšRiadok(pole, riadok); // Pred optimalizáciou for (int i = pole.length - 1; i > 0; --i) { for (int j = 0; j < i; ++j) if (pole[j] > pole[j + 1]) vymeň(j, j + 1); vypíšRiadok(pole); } vypíšRiadok(); for (int i = 0; i < pole.length; ++i) pole[i] = (int)náhodnéCeléČíslo(-5, 20); vypíšRiadok(pole, riadok); // Po optimalizácii { int koniec = pole.length - 1; do { int novýKoniec = 0; for (int i = 0; i < koniec; ++i) { if (pole[i] > pole[i + 1]) { vymeň(i, i + 1); novýKoniec = i; } } koniec = novýKoniec; vypíšRiadok(pole); } while (koniec != 0); } } public static void main(String[] args) { použiKonfiguráciu("BubbleSort.cfg"); new BubbleSort(); } }
- Animovaná prezentácia triedenia vkladaním – insertion sort (2015) 83,70 kB (81,74 KiB), 18. 3. 2015
Verzia v Pascale…
~
program triedenie_vkladanim; uses crt; const dlzka = 10; var pole: array [1 .. dlzka] of integer; i, j, c: integer; procedure vypis_pole; var i: integer; begin write(pole[1]:2); for i := 2 to dlzka do write(' ', pole[i]:2); writeln end; begin clrscr; randomize; for i := 1 to dlzka do begin write('Zadaj prvok ', i, ': '); { readln(pole[i]) } pole[i] := -5 + random(25); writeln(pole[i]) end; writeln; vypis_pole; writeln; { Pred optimalizáciou } for i := 2 to dlzka do { Začíname od druhého prvku... } begin c := pole[i]; j := i; while (j > 1) and (c < pole[j - 1]) do begin pole[j] := pole[j - 1]; dec(j) { j := j - 1 } end; pole[j] := c; vypis_pole end; writeln; for i := 1 to dlzka do begin write('Zadaj prvok ', i, ': '); { readln(pole[i]) } pole[i] := -5 + random(25); writeln(pole[i]) end; writeln; vypis_pole; writeln; { Po optimalizácii } for i := 2 to dlzka do begin c := pole[i]; j := i - 1; while (j >= 1) and (pole[j] > c) do begin pole[j + 1] := pole[j]; dec(j) end; pole[j + 1] := c; vypis_pole end; readln end.
Verzia v Jave pracujúca s verziou frameworku GRobot 1.75 (na sfunkčnenie s nižšími verziami treba zdrojový kód upraviť; s vyššími verziami sfunkčnenie programu môže/nemusí vyžadovať zásahy)…
~
import knižnica.GRobot; import static knižnica.GRobot.Svet.*; public class InsertionSort extends GRobot { private Zoznam<Integer> zoznam = new Zoznam<Integer>(); private int pole[]; private InsertionSort() { // Verzia so zoznamom for (int i = 0; i < 10; ++i) zoznam.pridaj((int)náhodnéCeléČíslo(-5, 20)); vypíšRiadok(zoznam, riadok); // Pred optimalizáciou for (int i = 1; i < zoznam.veľkosť(); ++i) // Začíname od druhého prvku… { int c = zoznam.daj(i); int j = i; while ((j > 0) && (c < zoznam.daj(j - 1))) { zoznam.vymeň(j, j - 1); --j; } zoznam.prepíš(j, c); vypíšRiadok(zoznam); } vypíšRiadok(); zoznam.vymaž(); for (int i = 0; i < 10; ++i) zoznam.pridaj((int)náhodnéCeléČíslo(-5, 20)); vypíšRiadok(zoznam, riadok); // Po optimalizácii for (int i = 1; i < zoznam.veľkosť(); ++i) // Začíname od druhého prvku… { int c = zoznam.daj(i); int j = i - 1; while (j >= 0 && zoznam.daj(j) > c) { zoznam.vymeň(j + 1, j); --j; } zoznam.prepíš(j + 1, c); vypíšRiadok(zoznam); } vypíšRiadok(); // Verzia s poľom pole = new int[10]; for (int i = 0; i < pole.length; ++i) pole[i] = (int)náhodnéCeléČíslo(-5, 20); vypíšRiadok(pole, riadok); // Po optimalizácii for (int i = 1; i < pole.length; ++i) { int c = pole[i]; int j = i - 1; while (j >= 0 && pole[j] > c) { pole[j + 1] = pole[j]; --j; } pole[j + 1] = c; vypíšRiadok(pole); } } public static void main(String[] args) { použiKonfiguráciu("InsertionSort.cfg"); new InsertionSort(); } }
- Animovaná prezentácia triedenia výberom – selection sort (2015) 70,94 kB (69,27 KiB), 18. 3. 2015
Verzia v Pascale…
~
program triedenie_vyberom; uses crt; const dlzka = 10; var pole: array [1 .. dlzka] of integer; i, lavy, pravy, min, max: integer; procedure vymen(i, j: integer); var c: integer; begin c := pole[i]; pole[i] := pole[j]; pole[j] := c end; procedure vypis_pole; var i: integer; begin write(pole[1]:2); for i := 2 to dlzka do write(' ', pole[i]:2); writeln end; begin clrscr; randomize; for i := 1 to dlzka do begin write('Zadaj prvok ', i, ': '); { readln(pole[i]) } pole[i] := -5 + random(25); writeln(pole[i]) end; writeln; vypis_pole; writeln; lavy := 1; pravy := dlzka; while lavy < pravy do begin { Hľadanie minima a maxima } min := lavy; { Nepracujeme s hodnotou min/max, ale s polohou! } max := lavy; for i := lavy + 1 to pravy do begin if pole[min] > pole[i] then min := i; if pole[max] < pole[i] then max := i end; { Umiestnenie prvkov } vymen(min, lavy); if max = lavy then { Ak sme našli maximum na pozícii "lavy", tak v tejto chvíli sa už nachádza na pozícii "min". } vymen(min, pravy) else vymen(max, pravy); inc(lavy); { lavy := lavy + 1; } dec(pravy); { pravy := pravy - 1 } vypis_pole end; readln end.
Verzia v Jave pracujúca s verziou frameworku GRobot 1.75 (na sfunkčnenie s nižšími verziami treba zdrojový kód upraviť; s vyššími verziami sfunkčnenie programu môže/nemusí vyžadovať zásahy)…
~
import knižnica.GRobot; import static knižnica.GRobot.Svet.*; public class SelectionSort extends GRobot { private Zoznam<Integer> zoznam = new Zoznam<Integer>(); private int pole[]; private void vymeň(int i, int j) { int c = pole[i]; pole[i] = pole[j]; pole[j] = c; } private SelectionSort() { // Verzia so zoznamom for (int i = 0; i < 10; ++i) zoznam.pridaj((int)náhodnéCeléČíslo(-5, 20)); vypíšRiadok(zoznam, riadok); { int ľavý = 0; int pravý = zoznam.veľkosť() - 1; while (ľavý < pravý) { // Hľadanie minima a maxima int min = ľavý; // Nepracujeme s hodnotou min/max, ale s polohou! int max = ľavý; for (int i = ľavý + 1; i <= pravý; ++i) { if (zoznam.daj(min) > zoznam.daj(i)) min = i; if (zoznam.daj(max) < zoznam.daj(i)) max = i; } // Umiestnenie prvkov zoznam.vymeň(min, ľavý); if (max == ľavý) // Ak sme našli maximum na pozícii „ľavý“, tak v tejto // chvíli sa už nachádza na pozícii „min“. zoznam.vymeň(min, pravý); else zoznam.vymeň(max, pravý); // Posúvanie hraníc ++ľavý; --pravý; vypíšRiadok(zoznam); } } vypíšRiadok(); // Verzia s poľom pole = new int[10]; for (int i = 0; i < pole.length; ++i) pole[i] = (int)náhodnéCeléČíslo(-5, 20); vypíšRiadok(pole, riadok); { int ľavý = 0; int pravý = pole.length - 1; while (ľavý < pravý) { // Hľadanie minima a maxima int min = ľavý; // Nepracujeme s hodnotou min/max, ale s polohou! int max = ľavý; for (int i = ľavý + 1; i <= pravý; ++i) { if (pole[min] > pole[i]) min = i; if (pole[max] < pole[i]) max = i; } // Umiestnenie prvkov vymeň(min, ľavý); if (max == ľavý) vymeň(min, pravý); else vymeň(max, pravý); // Posúvanie hraníc ++ľavý; --pravý; vypíšRiadok(pole); } } } public static void main(String[] args) { použiKonfiguráciu("SelectionSort.cfg"); new SelectionSort(); } }
- Java aplikácia simulujúca algoritmus rýchleho triedenia – quicksort (2015) 183,54 kB (179,24 KiB), 3. 4. 2017
Verzia v Pascale…
~
program rychle_triedenie; uses crt; const dlzka = 10; var pole: array[1 .. dlzka] of integer; procedure napln_pole; var i: integer; begin for i := 1 to dlzka do begin write('Zadaj prvok ', i, ': '); { readln(pole[i]) } pole[i] := -5 + random(25); writeln(pole[i]) end end; procedure vymen(i, j: integer); var c: integer; begin c := pole[i]; pole[i] := pole[j]; pole[j] := c end; procedure vypis_pole; var i: integer; begin write(pole[1]:2); for i := 2 to dlzka do write(' ', pole[i]:2); writeln end; procedure quicksort(lo, hi: integer); var i, j, pivot: integer; begin pivot := pole[(lo + hi) div 2]; i := lo; j := hi; while i <= j do begin while pole[i] < pivot do inc(i); while pole[j] > pivot do dec(j); if i <= j then begin vymen(i, j); inc(i); dec(j) end end; vypis_pole; if lo < j then quicksort(lo, j); if i < hi then quicksort(i, hi) end; begin clrscr; randomize; napln_pole; vypis_pole; quicksort(1, dlzka); readln end.
Verzia v Jave pracujúca s verziou frameworku GRobot 1.75 (na sfunkčnenie s nižšími verziami treba zdrojový kód upraviť; s vyššími verziami sfunkčnenie programu môže/nemusí vyžadovať zásahy)…
~
import knižnica.GRobot; import static knižnica.GRobot.Svet.*; public class Quicksort extends GRobot { private Zoznam<Integer> zoznam = new Zoznam<Integer>(); private int pole[]; private void vymeň(int i, int j) { int c = pole[i]; pole[i] = pole[j]; pole[j] = c; } private Quicksort() { // K verzii so zoznamom for (int i = 0; i < 10; ++i) zoznam.pridaj((int)náhodnéCeléČíslo(-5, 20)); vypíšRiadok(zoznam, riadok); quicksort_zoznam(); vypíšRiadok(); // K verzii s poľom pole = new int[10]; for (int i = 0; i < pole.length; ++i) pole[i] = (int)náhodnéCeléČíslo(-5, 20); vypíšRiadok(pole, riadok); quicksort_pole(); } // Verzia so zoznamom private void quicksort_zoznam(int lo, int hi) { int pivot = zoznam.daj((lo + hi) / 2); int i = lo, j = hi; while (i <= j) { while (zoznam.daj(i) < pivot) ++i; while (zoznam.daj(j) > pivot) --j; if (i <= j) zoznam.vymeň(i++, j--); // i a j zmenia hodnotu až po výmene } vypíšRiadok(zoznam); if (lo < j) quicksort_zoznam(lo, j); if (i < hi) quicksort_zoznam(i, hi); } public void quicksort_zoznam() { quicksort_zoznam(0, zoznam.dĺžka() - 1); } // Verzia s poľom public void quicksort_pole(int lo, int hi) { int pivot = pole[(lo + hi) / 2]; int i = lo, j = hi; while (i <= j) { while (pole[i] < pivot) ++i; while (pole[j] > pivot) --j; if (i <= j) vymeň(i++, j--); // i a j zmenia hodnotu až po výmene } vypíšRiadok(pole); if (lo < j) quicksort_pole(lo, j); if (i < hi) quicksort_pole(i, hi); } public void quicksort_pole() { quicksort_pole(0, pole.length - 1); } public static void main(String[] args) { použiKonfiguráciu("Quicksort.cfg"); new Quicksort(); } }