Triedenia (rôzne verzie a podklady)

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();
	}
}