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

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

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

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

Táto stránka obsahuje opis postupu pri implementácii algoritmu triedenia výberom (anglicky selection sort). Stránka nadväzuje na stránku s opisom implementácie algoritmu triedenia vkladaním. Odporúčame sa pred štúdiom tejto stránky najskôr zaoberať pochopením uvedeného algoritmu.

 

Algoritmus triedenia výberom pozostáva z nasledujúcich krokov:

  • nastavenie intervalu prehľadávania poľa na celý rozsah (všetky prvky),
  • [A] hľadanie minima, prípadne aj maxima, v rámci aktuálneho rozsahu,
  • presunutie nájdeného minima na začiatok aktuálneho rozsahu,
  • ak hľadáme aj maximum, tak nájdené maximum treba presunúť na koniec aktuálneho rozsahu, pričom treba dať pozor, či presúvame správny prvok,
  • zúženie rozsahu:
  • ak hľadáme len minimum, tak zvýšime spodnú hranicu intervalu,
  • ak hľadáme aj maximum, tak zároveň znížime aj hornú hranicu intervalu,
  • opakovanie od bodu [A] (ak je to ešte možné).

Všimnite si, že o hľadaní maxima sa hovorí ako o nepovinnom kroku. To naznačuje, ako môžu vyzerať rôzne verzie algoritmu.

Pozrite si nasledujúce video, ktoré ukazuje fungovanie algoritmu hľadajúceho minimum aj maximum v osemprvkovom poli vrátane špeciálnych prípadov: http://cec.​truni.​sk/​video/​selection­‑sort/​ otvárané v novom okne
(obvykle ide o externý odkaz) (video je bez komentára).

 

Budeme postupovať podobne ako pri algoritme triedenia vkladaním. Stručne si zopakujme niektoré informácie:

Nasledujúca definícia triedy je východiskovou šablónou. Je odvodená od triedy ikonaKonzola.java. otvárané v novom okne
(obvykle ide o externý odkaz) 231,00 B (231,00 B), 29. 12. 2016 Obsahuje definíciu poľa, jeho naplnenie náhodnými prvkami a metódu vymeň, ktorú budeme v rámci algoritmu používať. V nej budeme ďalej postupne rozvíjať metódu triediaceho algoritmu selectionSort.

~

public class Triedenia extends Konzola
{
	private int pole[] = new int[10];

	private Triedenia()
	{
		for (int i = 0; i < pole.length; ++i)
			pole[i] = (int)náhodnéCeléČíslo(0, 20);

		vypíšRiadok(pole);
		selectionSort();
		vypíšRiadok(pole);
	}

	public void selectionSort()
	{
		/*# Sem budeme vkladať ďalší kód. */
	}

	/**
	 * Táto metóda vymieňa hodnoty prvkov poľa na základe zadaných indexov
	 * i a j.
	 */
	public void vymeň(int i, int j)
	{
		int c = pole[i];
		pole[i] = pole[j];
		pole[j] = c;
	}

	public static void main (String[] args)
	{
		new Triedenia();
	}
}

 

Všetky ďalšie zmeny budeme vykonávať v tele metódy selectionSort, pričom celý postup rozdelíme na tri fázy označené písmenami ac, ktoré budú jemnejšie rozdelené poradovými číslami. Cieľom fázy a bude vyvinúť hľadanie minima a maxima tak, aby to spĺňalo požiadavky algoritmu. Fáza b bude mať za cieľ vyvinutie spôsobu opakovania všetkých krokov algoritmu (t. j. zostavenie cyklu) od bodu, ktorý je vyššie označený symbolom [A] a to vrátane posúvania hraníc prehľadávaného intervalu. Vo fáze c bude našou úlohou všetko spojiť a algoritmus dokončiť.

 

Najskôr si zopakujme algoritmus hľadania minima. Algoritmus zostavme tak, aby výsledok (iMin) bol index (t. j. poloha) najmenšieho nájdeného prvu poľa – minima. Postupujeme tak, že najprv zvolíme za minimum prvý prvok poľa (s indexom 0) a potom prehľadáme zvyšok poľa (od indexu 1 do indexu dĺžky, vynímajúc index rovný dĺžke poľa), či sa na niektorej pozícii nenachádza menší prvok (čo je vysoko pravdepodobné).

Porovnávame hodnoty prvkov poľa, ale pamätáme si index, t. j. pozíciu prvku poľa. Pamätáme si vždy index takého prvku, ktorého hodnota je menšia než hodnota prvku na naposledy zapamätanej pozícii.

~

int iMin = 0;

for (int i = 1; i < pole.length; ++i)
{
	if (pole[iMin] > pole[i]) iMin = i;
}

vypíšRiadok("Minimum bolo nájdené na pozícii ", iMin);

Po prehľadaní celého poľa budeme mať zaručené, že sme si zapamätali práve hodnotu pozície najmenšieho prvku poľa. Môže sa stať, že sa v poli vyskytne hodnota minima viac ráz. V takom prípade si algoritmus zapamätá pozíciu prvého nájdeného minima. (Nezabúdajme, že prvý prvok je na pozícii s indexom nula.) Po otestovaní môžeme príkaz výpisu vymazať.

(Prejdite do fázy a2.)

Algoritmus hľadania maxima je rovnaký, len namiesto znamienka > treba dosadiť znamienko < a treba mať definovanú samostatnú premennú na zapamätanie indexu maxima. Obidva algoritmy môžeme spojiť do jedného a hľadať minimum aj maximum naraz:

~

int iMin = 0, iMax = 0;

for (int i = 1; i < pole.length; ++i)
{
	if (pole[iMin] > pole[i]) iMin = i;
	if (pole[iMax] < pole[i]) iMax = i;
}

vypíšRiadok("Minimum je na pozícii ", iMin, " = ", pole[iMin]);
vypíšRiadok("Maximum je na pozícii ", iMax, " = ", pole[iMax]);

Príkazy výpisu môžeme po úspešnom otestovaní tejto časti algoritmu vymazať. Táto fáza ešte nie je dokončená, ale teraz musíme začať pracovať s inou časťou algoritmu. Prejdime k fáze b.

(Prejdite do fázy b1.)

Vonkajší cyklus tohto triediaceho algoritmu má zabezpečiť, aby sa interval prehľadávania poľa postupne zužoval. Na začiatku sa bude prehľadávať celé pole, to znamená, že interval bude definovaný od indexu nula po index rovný dĺžke poľa mínus jeden (vrátane).

Interval sa bude postupne zužovať dokedy bude neprázdny. Za prázdny interval budeme považovať taký, ktorého horná hranica je menšia alebo rovná než spodná. Podmienka cyklu while určuje okolnosti, za akých má zmysel vykonávať itácie. To je presne vtedy, keď je interval prehľadávania neprázdny, to znamená, že horná hranica je väčšia než spodná.

Syntaktický zápis uvedeného opisu bude v jazyku Java vyzerať takto:

~

int lo = 0;
int hi = pole.length - 1;

while (lo < hi)
{

	++lo;
	--hi;
}

(Prejdite do fázy b2.)

V jazyku Java je možné každý cyklus for prepísať na cyklus while. Naopak to platiť nemusí, ale tento typ cyklu while sa na cyklus for prepísať dá. Symbolický zápis celej hlavičky cyklu v jednom riadku môže byť pre niekoho prehľadný, pre iného naopak ťažšie zrozumiteľný. Napriek tomu a práve preto je dobré o takomto spôsobe zápisu vedieť – aby ste mu v prípade, že sa s ním stretnete vedeli porozumieť.

Označme komentárom jednotlivé časti cyklu while (vrátane tých, ktoré sú mimo tela cyklu, ale bez ktorých by cyklus nefungoval):

~

// inicializácia
int lo = 0;
int hi = pole.length - 1;

while (lo < hi) // podmienka
{

	// iteračné príkazy zabezpečujúce takú zmenu hodôt riadiacich
	// premenných, aby sa cyklus neopakoval donekonečna
	++lo;
	--hi;
}

Presne také prvky očakáva hlavička cyklu for:

~

for («inicializácia»; «podmienka»; «iteračný príkaz»)
{
}

Inicializácia sa dá spojiť do jedného riadka (resp. príkazového celku) takto:

~

int lo = 0, hi = pole.length - 1;

Čiže jednotlivé definície premenných sme oddelili čiarkou a celok sme ukončili bodkočiarkou. Akoby sme bodkočiarku medzi príkazmi nahradili čiarkou s tým, že obidve definície musia mať rovnaký údajový typ (v našom prípade int).

Podobne je možné bodkočiarku (;) „nahradiť“ čiarkou (,) na oddelenie jednotlivých iteračných príkazov. Výsledok bude vyzerať takto:

~

for (int lo = 0, hi = pole.length - 1; lo < hi; ++lo, --hi)
{

}

(Prejdite do fázy a3.)

Vráťme sa k fáze a. Algoritmus prehľadávania celého poľa musíme upraviť na algoritmus prehľadávania intervalu. Pri úprave algoritmu hľadania minima a maxima pre potreby tohto triediaceho algoritmu treba dbať na dve veci:

  1. Prvé vykonanie hľadania minima a maxima musí prehľadať celé pole.
  2. Ďalšie vykonania musia byť vykonané na rovnomerne sa zmenšujúcom intervale.

To znamená, že nemôžeme začať hľadať na fixnej pozícii s indexom 0, ale na pozícii, ktorá sa bude s časom meniť. Podobne horná hranica intervalu nebude stále totožná s prvkom na pozíci s indexom dĺžka poľa mínus jeden, ale sa bude meniť.

Pred vykonaním úprav urobíme jednu drobnú zmenu, ktorá môže uľahčiť pochopenie toho, prečo bolo vykonané nahradenie pevných hodnôt premenlivými hodnotami hraníc intervalu práve tým spôsobom ako sa to pripravujme urobiť.

Ide o to, že v tejto súvislosti a v tomto prípade je výhodnejšie určiť koniec opakovania cyklu for nie v tvare i < «dĺžka poľa», ale v tvare i <= «dĺžka poľa» ­‑ 1:

~

int iMin = 0, iMax = 0;

for (int i = 1; i <= pole.length - 1; ++i)
{
	if (pole[iMin] > pole[i]) iMin = i;
	if (pole[iMax] < pole[i]) iMax = i;
}

V princípe ide o rovnakú podmienku (pri celých číslach je porovnanie menší než hodnota totožné s porovnaním menší alebo rovný než hodnota mínus jeden), ale za normálnych okolností by bolo nevýhodné použiť pri stanovení podmienky nadbytočný výpočet «dĺžka poľa» ­‑ 1. Teraz sme však vykonali túto náhradu účelovo. O chvíľu podotkneme, že hodnota premennej hi začína klesať presne na hodnote dĺžky poľa mínus jeden a to nás zaujíma.

(Prejdite do fázy a4.)

Zopakujme si dva body, ktoré budeme dodržiavať pri úprave algoritmu hľadania minima a maxima pre potreby tohto triediaceho algoritmu:

  1. Prvé vykonanie hľadania minima a maxima musí prehľadať celé pole.
  2. Ďalšie vykonania musia byť vykonané na rovnomerne sa zmenšujúcom intervale.

(Zmenu v algoritme hľadania minima a maxima opísanú vo fáze a3 sme vykonali presne v súlade s dodržaním vyššie uvedeného prvého bodu – konkrétne na uľahčenie zmeny súvisiacej s hornou hranicou intervalu.)

Niektorí z Vás zrejme vytušili, že budeme využívať hodnoty uložené v premenných lohi (zavedených vo fáze b). Vieme, že hodnoty obidvoch premenných sa menia v súlade s bodom dva, takže ak použijeme tieto premenné, tak tomuto bodu nemusíme ďalej venovať pozornosť.

Skúsme teda do algoritmu hľadania minima a maxima dosadiť hodnoty hraníc intervalu lohi, pričom priebežne overujme to, či je dodržaný prvý bod a ak nie je, tak nájdime spôsob ako to napraviť.

Pôvodný algoritmus najprv zvolí za minimum (zároveň aj za maximum) prvý prvok poľa (s indexom nula). Teraz to bude prvý prvok intervalu. Keďže pri prvom vykonaní je hranica lo rovná nule, môžeme priamo napísať:

~

int iMin = lo, iMax = lo;

Algoritmus začína prehľadávanie na druhom prvku poľa (s indexom 1). Teraz to bude prvok, ktorý nasleduje tesne za začiatkom intervalu. To môžeme vyriešiť výpočtom lo + 1, takže zapíšeme:

~

for (int i = lo + 1; i <= pole.length - 1; ++i)

Horná hranica cyklu for je momentálne stanovená podmienkou pole.length ­‑ 1. Presne na tej hodnote začína klesať horná hranica intervalu prehľadávania hi, takže môžeme dosadiť (práve preto sme vo fáze a3 vykonali zdanlivo nevýhodnú zmenu z takej podmieky určujúcej hornú hranicu cyklu, ktorá používala operátor menší než a hornú hranicu dĺžky poľa bezo zmeny na takú podmienku, ktorá využívala operátor menší alebo rovný než a výpočet na určenie hornej hranice cyklu z dĺžky poľa mínus jeden; teraz sa táto nevýhoda stratí, lebo výpočet zmizne; pre niekoho by bolo možno jednoduchšie, keby sme fázu a3 vynechali – vtedy by na tomto mieste vznikol iný výpočet, ktorý by sme následne odstránili a tým by sme dostali rovnaký výsledok ako teraz):

~

for (int i = lo + 1; i <= hi; ++i)

Toto je celý upravený algoritmus prehľadávania:

~

int iMin = lo, iMax = lo;

for (int i = lo + 1; i <= hi; ++i)
{
	if (pole[iMin] > pole[i]) iMin = i;
	if (pole[iMax] < pole[i]) iMax = i;
}

Ten neskôr umiestnime do vonkajšieho cyklu triediaceho algoritmu (vytvoreného vo fáze b).

(Prejdite do fázy a5.)

Na záver tejto fázy urobíme jednu malú syntaktickú úpravu. Vo fáze b2 sme syntakticky spájali hlavičku vonkajšieho cyklu do jedného riadku. Podobnú úpravu môžeme urobiť aj pri tomto algoritme, ale jeden riadok sa nám nepodarí dosiahnuť – deklarácie premenných iMiniMax musíme oddeliť, pretože ich hodnoty budeme potrebovať aj po skončení cyklu:

~

// Deklarácie:
int iMin, iMax;

// Inicializácie:
iMin = lo;
iMax = lo;

Keďže priradenie je v jazyku Java vždy vnímané ako plnohodnotná binárna operácia, ktorá prijíma dva operandy a poskytuje výsledok (výsledkom je priradená hodnota), môžeme napísať:

~

iMin = iMax = lo;

Tento výraz môžeme vložiť do zátvorky namiesto premennej lo vo výraze inicializácie cyklu int i = lo + 1:

~

for (int i = (iMin = iMax = lo) + 1; i <= hi; ++i)

Takto upravený algoritmus hľadania minima a maxima vložíme do vonkajšieho cyklu triediaceho algoritmu.

(Prejdite do fázy c1.)

Toto je finálna fáza, v ktorej všetko spojíme. V predchádzajúcej fáze sme pripravili algoritmus hľadania minima a maxima na vloženie do vnútra vonkajšieho cyklu triediaceho algoritmu.

To znamená, že algoritmus hľadania minima a maxima sa stane vnútorným cyklom tiediaceho algoritmu. V skutočnosti by už v terajšom štádiu úprav mimo tela vonkajšieho cyklu (t. j. samostatne) nefungoval, pretože používa premenné definované práve v rámci vonkajšieho cyklu (lohi).

Zlúčenie obidvoch cyklov bude vyzerať takto:

~

for (int lo = 0, hi = pole.length - 1; lo < hi; ++lo, --hi)
{
	int iMin, iMax;

	for (int i = (iMin = iMax = lo) + 1; i <= hi; ++i)
	{
		if (pole[iMin] > pole[i]) iMin = i;
		if (pole[iMax] < pole[i]) iMax = i;
	}

}

Teraz potrebujeme zabezpečiť spracovanie nájdených prvkov (minima a maxima).

(Prejdite do fázy c2.)

Teraz potrebujeme zabezpečiť spracovanie nájdených prvkov (minima a maxima). Urobíme tak tesne po skončení cyklu hľadajúceho minimum a maximum:

~

for (int lo = 0, hi = pole.length - 1; lo < hi; ++lo, --hi)
{
	int iMin, iMax;

	for (int i = (iMin = iMax = lo) + 1; i <= hi; ++i)
	{
		if (pole[iMin] > pole[i]) iMin = i;
		if (pole[iMax] < pole[i]) iMax = i;
	}

	/*# Sem vložíme riadky spracúvajúce nájdené minimum a maximum. */
}

Keby sme nepotrebovali uvažovať o vzniknutí žiadnych špeciálnych situácií, stačilo by jednoducho presunúť minimum na začiatok prehľadávaného intervalu a maximum na jeho koniec:

~

vymeň(iMin, lo);
vymeň(iMax, hi);

Problém je, že špeciálna situácia môže nastať. Je ňou prípad, kedy sa nájdené maximum nachádza na pozícii začiatku prehľadávaného intervalu (algoritmicky zapísané keď iMax == lo). Prvá výmena totiž v takom prípade presunie nájdené maximum na pozíciu nájdeného minima. To znamená, že tento prípad musíme odlíšiť a keď táto situácia vznikne, musíme namiesto druhej výmeny vykonať príkaz vymeň(iMin, hi). Čiže všetky prípady výmeny budú vyzerať takto:

~

vymeň(iMin, lo);
if (iMax == lo) vymeň(iMin, hi);
else vymeň(iMax, hi);

(Prejdite do fázy c3.)

Algoritmus triedenia výberom teraz vyzerá takto:

~

for (int lo = 0, hi = pole.length - 1; lo < hi; ++lo, --hi)
{
	int iMin, iMax;

	for (int i = (iMin = iMax = lo) + 1; i <= hi; ++i)
	{
		if (pole[iMin] > pole[i]) iMin = i;
		if (pole[iMax] < pole[i]) iMax = i;
	}

	vymeň(iMin, lo);
	if (iMax == lo) vymeň(iMin, hi);
	else vymeň(iMax, hi);
}

Poslednou úpravou je malé zvýšenie efektívnosti zabránením vykonania výmeny v takom prípade, že sa algoritmus pokúša vymeniť prvok sám so sebou (aj také prípadny nastávajú – keď je minimum nájdené na začiatku prehľadávaného intervalu alebo maximum na jeho konci).

To znamená, že pred každú výmenu musíme vložiť podmienku, ktorá overí, či má výmena zmysel. Pri tom je dobré uvedomiť si, že ak vynecháme prvú výmenu, tak už nemusíme kontrolovať špeciálny prípad pred vykonaním druhej výmeny, čiže môžeme zapísať:

~

if (iMin != lo)
{
	vymeň(iMin, lo);
	if (iMax == lo) vymeň(iMin, hi);
	else vymeň(iMax, hi);
}
else
{
	vymeň(iMax, hi);
}

Teraz stačí doplniť overenie zmyslu vykonania druhej výmeny, čím sa dostaneme k takémuto zápisu:

~

if (iMin != lo)
{
	vymeň(iMin, lo);
	if (iMax == lo)
	{
		// vytvorenie tohto bloku je povinné
		if (iMin != hi) vymeň(iMin, hi);
	}
	else if (iMax != hi) vymeň(iMax, hi);
}
else
{
	vymeň(iMax, hi);
}

Pri tom sme museli vytvoriť ďalší blok, inak by bola vetva else nesprávne priradená k vnútornej podmienke iMin != hi, čo by bola chyba.

(Zobrazte výsledok.)

Úplne dokončená metóda selectionSort:

~

void selectionSort()
{
	for (int lo = 0, hi = pole.length - 1; lo < hi; ++lo, --hi)
	{
		int iMin, iMax;

		for (int i = (iMin = iMax = lo) + 1; i <= hi; ++i)
		{
			if (pole[iMin] > pole[i]) iMin = i;
			if (pole[iMax] < pole[i]) iMax = i;
		}

		if (iMin != lo)
		{
			vymeň(iMin, lo);
			if (iMax == lo)
			{
				// ak iMax == lo, znamená to, že iMax je na pozícii iMin…
				if (iMin != hi) vymeň(iMin, hi);
			}
			else if (iMax != hi) vymeň(iMax, hi);
		}
		else
		{
			if (iMax != hi) vymeň(iMax, hi);
		}
	}
}