TlačiťTlačiť Slovenčina English Hľadať RSS

© 2005 – 2024 Roman Horváth, všetky práva vyhradené. Dnes je 29. 3. 2024.

Stránka sa načítava, prosím čakajte…

Dátum: 25. 3. 2014, pred viacerými rokmi, aktualizované: 6. 4. 2015, pred niekoľkými rokmi

Poznámka: Tento projekt je starší. Bude potrebné ho aktualizovať tak, aby bol kompatibilný s najnovšou verziou programovacieho rámca GRobot.

Na tejto stránke je publikovaný zdrojový kód triedy, ktorá realizuje porovnanie niekoľkých implementácií rôznych triediacich algoritmov. Výkon každého algoritmu je závislý od implementácie, v prípade jazyka Java aj od spôsobu interpretácie bajtkódu virtuálnym strojom a tiež od iných faktorov (napríklad od použitia hardvérového urýchlenia virtuálnym strojom), takže rovnaké implementácie algoritmov môžu poskytovať rôzne výsledky na rôznych platformách alebo počítačoch.

Aj napriek negrafickej orientácii kódu sú v ňom používané niektoré časti skupiny tried grafického robota. otvárané v novom okne
(obvykle ide o externý odkaz) Na vygenerovanie prázdneho projektu odporúčam použiť Generátor projektov BlueJ (dostupný v sekcii Softvér na prevzatie).

~

/**
 * Vitajte vo veľkej súťaži triedení! Pred začatím súťaže musíme stanoviť
 * pravidlá súťaže!<br />
 *
 * (1) Na to, aby boli výsledky jednotlivých triedení porovnateľné, musíme
 * zabezpečiť, aby všetky algoritmy (a ich optimalizované verzie) triedili
 * rovnaké (t. j. rovnako neusporiadané) zoznamy.<br />
 *
 * (2) Na to, aby boli výsledky jednotlivých testov objektívne, musíme
 * zabezpečiť, aby každý algoritmus mal možnosť triediť pestrú paletu rôzne
 * neusporiadaných zoznamov. Zároveň by zoznamy mali byť dostatočne
 * veľké.<br />
 *
 * Dodržanie týchto pravidiel súťaženia zabezpečíme vygenerovaním veľkého
 * množstva predlôh dostatočne veľkých zoznamov, ktoré potom postupne
 * posunieme na zotriedenie jednotlivým algoritmom. Aby sme zvýšili
 * objektívnosť testov, necháme každý algoritmus zotriediť každý zoznam
 * niekoľko ráz.
 */
public class VeľkáSúťažTriedení extends GRobot
{
	// Predloha bude celočíselný zoznam
	private class Predloha extends Zoznam<Integer> {}

	// Definujeme zoznam predlôh, ktoré budeme postupne v sériách testov
	// posúvať algoritmom na triedenie
	private Zoznam<Predloha> predlohy = new Zoznam<Predloha>();

	// Tento súkromný atribút použijeme na určenie zoznamu, s ktorým budeme
	// pracovať počas jednej série testov
	private int čísloPredlohy = 0;

	// Toto bude pracovný zoznam, ktorého prvky budú triedené;
	// tento zoznam sa po každom teste vymaže a naplní znova…
	private Zoznam<Integer> zoznam = new Zoznam<Integer>();


	// Táto konštanta určuje počet predlôh, s ktorými budeme pracovať
	public final static int početPredlôh = 80;

	// Táto konštanta určuje počet prvkov v každej predlohe
	public final static int početPrvkov = 100;

	// Táto konštanta určuje, koľko testov bude vykonaných s tou istou
	// predlohou
	public final static int početTestov = 50;


	// Tento súkromný atribút poslúži na zaznamenávanie systémového času,
	// ktorý použijeme na meranie
	private long stopky = 0;


	// V konštruktore vykonáme a zobrazíme výsledky všetkých testov
	private VeľkáSúťažTriedení()
	{
		// Najskôr vygenerujeme predlohy
		for (int i = 0; i < početPredlôh; ++i)
		{
			Predloha predloha = new Predloha();

			for (int j = 0; j < početPrvkov; ++j)
				predloha.pridaj((int)Svet.náhodnéCeléČíslo(-50, 50));

			predlohy.pridaj(predloha);
		}

		// Chvíľu počkáme; pre istotu; aby sa stabilizovali všetky objekty
		// (keby bolo náhodou treba)…
		Svet.čakaj(1);


		// Nasleduje spúšťanie jednotlivých sérií testov…
		// (Vo viacerých prípadoch testujeme viacero verzií rovnakého
		// algoritmu, aby sme ukázali, akým spôsobom sa dá zvyšovať
		// efektívnosť. Vysvetlenie rozdielov medzi nimi je v komentároch
		// metód jednotlivých algoritmov.)

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) bubbleSort1();
		long bubbleSort1 = zastavČasomieru();

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) bubbleSort2();
		long bubbleSort2 = zastavČasomieru();

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) bubbleSort3();
		long bubbleSort3 = zastavČasomieru();

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) insertSort1();
		long insertSort1 = zastavČasomieru();

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) insertSort2();
		long insertSort2 = zastavČasomieru();

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) insertSort3();
		long insertSort3 = zastavČasomieru();

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) selectSort1();
		long selectSort1 = zastavČasomieru();

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) selectSort2();
		long selectSort2 = zastavČasomieru();

		spustiČasomieru();
		for (čísloPredlohy = 0; čísloPredlohy <
			predlohy.veľkosť(); ++čísloPredlohy)
			for (int i = 0; i < početTestov; ++i) quickSort();
		long quickSort = zastavČasomieru();


		// Nasleduje výpis výsledkov…

		Svet.vypíšRiadok("Výsledok algoritmu bubbleSort1",
			bubbleSort1, "ms.");
		Svet.vypíšRiadok("Výsledok algoritmu bubbleSort2",
			bubbleSort2, "ms.");
		Svet.vypíšRiadok("Výsledok algoritmu bubbleSort3",
			bubbleSort3, "ms.");
		Svet.vypíšRiadok("Výsledok algoritmu insertSort1",
			insertSort1, "ms.");
		Svet.vypíšRiadok("Výsledok algoritmu insertSort2",
			insertSort2, "ms.");
		Svet.vypíšRiadok("Výsledok algoritmu insertSort3",
			insertSort3, "ms.");
		Svet.vypíšRiadok("Výsledok algoritmu selectSort1",
			selectSort1, "ms.");
		Svet.vypíšRiadok("Výsledok algoritmu selectSort2",
			selectSort2, "ms.");
		Svet.vypíšRiadok("Výsledok algoritmu quickSort",
			quickSort, "ms.");
	}


	/**
	 * Táto metóda „spustí“ časomieru. V skutočnosti si iba zapamätá
	 * začiatočný systémový čas v milisekundách, ktorý potom použije na
	 * vypočítanie trvania jedného merania.
	 */
	public void spustiČasomieru()
	{
		stopky = System.currentTimeMillis();
	}

	/**
	 * Táto metóda „zastaví“ časomieru. V skutočnosti iba odčíta od aktuálneho
	 * systémového času v milisekundách čas, ktorý sme si zapamätali na
	 * začiatku merania v metóde „spustiČasomieru“.
	 */
	public long zastavČasomieru()
	{
		return stopky = System.currentTimeMillis() - stopky;
	}

	/**
	 * Táto metóda vyčistí pracovný zoznam a skopíruje do neho predlohu určenú
	 * indexom „čísloPredlohy“.
	 */
	public void zoznamPodľaPredlohy()
	{
		zoznam.vymaž();
		zoznam.pridaj(predlohy.daj(čísloPredlohy));
	}


	/**
	 * Toto je najmenej efektívna implementácia bublinkového triedenia. Na
	 * nízku efektívnosť má vplyv určenie horných hraníc cyklov výpočtami,
	 * ktoré spomaľujú vykonávanie algoritmu pri každej iterácii. Keď je
	 * iterácií veľa, spomaľujúci efekt sa výrazne prejaví.
	 */
	public void bubbleSort1()
	{
		zoznamPodľaPredlohy();

		for (int i = 0; i < zoznam.veľkosť() - 1; ++i)
		{
			for (int j = 0; j < zoznam.veľkosť() - i - 1; ++j)
			{
				if (zoznam.daj(j) > zoznam.daj(j + 1))
					zoznam.vymeň(j, j + 1);
			}
		}
	}


	/**
	 * V tejto verzii algoritmu sme sa zbavili neustále sa zbytočne
	 * opakujúcich výpočtov hraníc tým, že sme obrátili smerovanie cyklu zhora
	 * nadol. Výpočet hornej hranice je tak vykonaný len raz, na začiatku. Po
	 * vykonaní testov uvidíme, že zvýšenie efektívnosti je viditeľné na čase
	 * vykonávania, ktorý je zhruba 70%-ný oproti pôvodnej verzii.
	 */
	public void bubbleSort2()
	{
		zoznamPodľaPredlohy();

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


	/**
	 * Do tretice sa pokúšame zvýšiť efektívnosť zabezpečením skorého
	 * skončenia triedenia v prípade, že už nenastáva žiadna výmena prvkov.
	 * Toto vylepšenie má zmysel len pre niektoré usporiadania zoznamov.
	 * V prípadoch, kedy je neusporiadanosť zoznamu taká veľká, že je potrebné
	 * vykonávať triedenie do posledného prvku, je toto vylepšenie
	 * v skutočnosti na škodu, pretože výsledný algoritmus spomaľuje. Naopak,
	 * keď je zoznam takmer zotriedený a stačí len niekoľko výmen, algoritmus
	 * skončí veľmi skoro. Vtedy by týmto vylepšením získal. Problém je, že
	 * nevieme dopredu určiť do akej miery bude zoznam neusporiadaný. My
	 * robíme testy pre veľa rôzne neusporiadaných zoznamov, čím zabezpečujeme
	 * objektívnosť merania. Po spustení testov zistíme, že zisk tejto verzie
	 * algoritmu je malý. Keby sme nepoznali žiadny iný algoritmus, uspokojili
	 * by sme sa aj s takýmto drobným prírastkom efektívnosti. Vzhľadom na to,
	 * že realita je iná, je pre nás takýto prírastok zanedbateľný.
	 */
	public void bubbleSort3()
	{
		zoznamPodľaPredlohy();

		for (int i = zoznam.veľkosť() - 1; i > 0; --i)
		{
			boolean zastav = true;

			for (int j = 0; j < i; ++j)
			{
				if (zoznam.daj(j) > zoznam.daj(j + 1))
				{
					zoznam.vymeň(j, j + 1);
					zastav = false;
				}
			}

			if (zastav) break;
		}
	}


	/**
	 * Rôzne verzie triedenia vkladaním sa vzájomne odlišujú len minimálne.
	 * Algoritmus je implementačne relatívne jednoduchý, preto neposkytuje
	 * veľa priestoru na optimalizáciu. Prvá verzia je „prvoplánová“ bez
	 * pokusov o vylepšenia. (Vylepšenia sú opísané pri ďalších verziách
	 * algoritmov.)
	 */
	public void insertSort1()
	{
		zoznamPodľaPredlohy();

		for (int i = 1; i < zoznam.veľkosť(); ++i)
		{
			int a = zoznam.daj(i);
			int j = i;

			while ((j > 0) && (a < zoznam.daj(j - 1)))
			{
				zoznam.vymeň(j, j - 1);
				--j;
			}

			zoznam.prepíš(j, a);
		}
	}


	/**
	 * V tejto verzii sme skúsili zvýšiť efektívnosť zbavením sa neustáleho
	 * spúšťania metódy „veľkosť()“ v určení hornej hranice cyklu (to má za
	 * následok volanie metódy pri každej iterácii). Namiesto toho, aby sme
	 * hornú hranicu cyklu „for“ určili volaním metódy „zoznam.veľkosť()“, si
	 * pred vykonávaním cyklu uložíme hodnotu veľkosti zoznamu do premennej
	 * a tú použijeme na stanovenie podmienky hornej hranice cyklu. Po
	 * spustení testov zistíme, že istý časový zisk tu je. Nie extrémne veľký,
	 * ale predsa. Použitie premennej je rýchlejšie než volanie metódy.
	 * (Poznámka: takúto optimalizáciu smieme vykonať len pri takých
	 * algoritmoch, pri ktorých sme si istí, že veľkosť spracúvaného zoznamu
	 * sa počas vykonávania algoritmu nezmení. Našťastie v tomto prípade máme
	 * splnenie tejto podmienky zaručené.)
	 */
	public void insertSort2()
	{
		zoznamPodľaPredlohy();

		int veľkosť = zoznam.veľkosť();
		for (int i = 1; i < veľkosť; ++i)
		{
			int a = zoznam.daj(i);
			int j = i;

			while ((j > 0) && (a < zoznam.daj(j - 1)))
			{
				zoznam.vymeň(j, j - 1);
				--j;
			}

			zoznam.prepíš(j, a);
		}
	}


	/**
	 * V tretej verzii triedenia vkladaním skúšame nahradiť výmenu prvkov
	 * posunom. V tomto algoritme (ako jedinom triediacom algoritme z tých,
	 * ktoré sme preberali) nie je potrebná výmena prvkov, pretože prvky sa
	 * v skutočnosti len posúvajú. Výmena je v tomto prípade zbytočný luxus.
	 * Ale je tu jeden problém. Triedime zoznam. Zoznam je objekt, ktorého
	 * prvky čítame a zapisujeme volaním metód. Keby sme použili pole, ku
	 * ktorého prvkom pristupujeme priamo, zisk náhrady výmeny za posun prvkov
	 * by bol zreteľný. No po spustení testov zistíme, že v tomto prípade, keď
	 * používame zoznam, sme algoritmu v skutočnosti poškodili. Je to preto,
	 * že na prečítanie prvku zoznamu musíme volať metódu „daj“ a na zapísanie
	 * prvku do zoznamu zase metódu „prepíš“. To sú dve volania metód namiesto
	 * jedného („vymeň“). Preto sa v skutočnosti vykonávanie algoritmu
	 * spomalí. Síce minimálne, ale predsa. (Nuž: „nie je všetko čierne alebo
	 * biele.“)
	 */
	public void insertSort3()
	{
		zoznamPodľaPredlohy();

		int veľkosť = zoznam.veľkosť();
		for (int i = 1; i < veľkosť; ++i)
		{
			int a = zoznam.daj(i);
			int j = i;

			while ((j > 0) && (a < zoznam.daj(j - 1)))
			{
				zoznam.prepíš(j, zoznam.daj(j - 1));
				--j;
			}

			zoznam.prepíš(j, a);
		}
	}


	/**
	 * Prvá verzia algoritmu triedenia výberom nezahŕňa žiadne úsilie
	 * o optimalizáciu, o ktorej sa dá uvažovať v tej časti algoritmu,
	 * v ktorej sú vykonávané výmeny prvkov.
	 */
	public void selectSort1()
	{
		zoznamPodľaPredlohy();

		int ľavý = 0;
		int pravý = zoznam.veľkosť() - 1;

		while (ľavý < pravý)
		{
			int min = ľavý;
			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;
			}

			zoznam.vymeň(min, ľavý);
			if (max == ľavý)
				zoznam.vymeň(min, pravý);
			else
				zoznam.vymeň(max, pravý);

			++ľavý;
			--pravý;
		}
	}


	/**
	 * V tejto verzii algoritmu sa usilujeme obmedziť množstvo výmen. A to
	 * tak, že pred každou výmenou overujeme, či má alebo nemá zmysel
	 * (konkrétne, či nejde o pokus vymeniť prvok sám so sebou) a až po
	 * overení zavoláme metódu „vymeň“. V skutočnosti je metóda „vymeň“
	 * vnútorne optimalizovaná tak, aby sa v prípade, že sa pokúšame vymeniť
	 * prvok „sám so sebou“ výmena nevykonala. (My však predpokladáme, že to
	 * nevieme a nemáme to možnosť nijakým spôsobom zistiť, keďže táto
	 * skutočnosť nie je uvedená v dokumentácii.) Napriek tomu je táto verzia
	 * algoritmu zanedbateľne rýchlejšia. Malá úspora času, ktorú môžeme
	 * spozorovať je spôsobená len obmedzením počtu volaní metódy „vymeň“,
	 * pretože príkaz volania metódy nie je až taký náročný na vykonanie ako
	 * by bola séria príkazov vykonávajúca výmenu prvkov tým spôsobom, ktorý
	 * je opísaný v zdrojovom kóde triedy Vymeň. Môžeme povedať, že tento
	 * spôsob vylepšenia by mal skutočný zmysel predovšetkým v prípade, keby
	 * sme nepoužili optimalizovanú verziu metódy „vymeň“, ale nejakú vlastnú…
	 */
	public void selectSort2()
	{
		zoznamPodľaPredlohy();

		int ľavý = 0;
		int pravý = zoznam.veľkosť() - 1;

		while (ľavý < pravý)
		{
			int min = ľavý;
			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;
			}

			if (min != ľavý)
			{
				zoznam.vymeň(min, ľavý);
				if (max != ľavý) zoznam.vymeň(max, pravý);
				else if (min != pravý)zoznam.vymeň(min, pravý);
			}
			else if (max != pravý) zoznam.vymeň(max, pravý);

			++ľavý;
			--pravý;
		}
	}


	/**
	 * Algoritmus rýchleho triedenia sme implementovali len raz, pretože sme
	 * nenašli priestor na optimalizáciu. (Dve nasledujúce metódy s názvom
	 * „quickSort“, sú súčasťou tej istej implementácie.) Táto (prvá) metóda
	 * tvorí súkromné rekurzívne jadro algoritmu, druhá metóda tvorí obálku.
	 */
	private void quickSort(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--);
		}

		if (lo < j) quickSort(lo, j);
		if (i < hi) quickSort(i, hi);
	}


	/**
	 * Toto je verejná obálka algoritmu, ktorú potrebujeme, pretože do
	 * rekurzívneho jadra nemôžeme zaradiť žiadne príkazy pre potreby súťaže.
	 * Narušili by jeho činnosť. (Poznámka: názov metódy sme mohli recyklovať
	 * vďaka mechanizmu polymorfizmu v Jave, ktorý nazývame „preťažovanie“.)
	 */
	public void quickSort()
	{
		zoznamPodľaPredlohy();
		quickSort(0, zoznam.veľkosť() - 1);
	}


	// Nakoniec je tu hlavná metóda, ktorú, dúfam, netreba predstavovať…
	public static void main(String[] args)
	{
		Svet.použiKonfiguráciu("velka-sutaz-triedeni.cfg");
		new VeľkáSúťažTriedení();
	}
}