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: 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 vkladaním (anglicky insertion sort). Stránka nadväzuje na informácie získané pri implementácii algoritmu bublinkového triedenia (na hodinách). Odporúčame, aby ste sa pred štúdiom tejto stránky najskôr zaoberali dokonalým porozumením uvedeného algoritmu.

 

Algoritmus triedenia vkladaním pozostáva z nasledujúcich krokov:

  • nastavím ukazovateľ na druhý prvok v poli (pretože z princípu algoritmu vyplynie, že nemá zmysel začínať na prvom prvku poľa),
  • [A] nastavím aktuálnu pozíciu (ukazujúcu na aktuálny prvok) na hodnotu ukazovateľa,
  • aktuálny prvok vložím do pomocnej premennej,
  • [B] porovnám hodnotu prvku, ktorý je prvý zľava od aktuálnej pozície s hodnotou pomocnej premennej: ak je hodnota porovnaného prvku väčšia, presuniem (skopírujem) ho na aktuálnu pozíciu a presuniem sa o jednu pozíciu doľava,
  • opakujem bod [B] dokedy je možné posúvať sa viac doľava a súčasne je prvok naľavo väčší od hodnoty pomocnej premennej,
  • vložím hodnotu pomocnej premennej na aktuálnu pozíciu,
  • ak je to možné (ak sa dá posúvať doprava), tak zvýšim hodnotu ukazovateľa (čiže posuniem ukazovateľ doprava) a zopakujem algoritmus od bodu [A].

Pozrite si nasledujúce video, ktoré ukazuje použitie algoritmu na zotriedenie osemprvkového poľa: http://cec.​truni.​sk/​video/​insertion­‑sort/​ otvárané v novom okne
(obvykle ide o externý odkaz) (video je bez komentára).

 

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, výpis prvkov poľa pred volaním metódy insertionSort, volanie metódy insertionSort a výpis prvkov poľa po jej volaní.

~

public class HlavnáTrieda extends Konzola
{
	private int pole[] = new int[10];

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

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

	public void insertionSort()
	{
		
	}

	public static void main(String[] args)
	{
		new HlavnáTrieda();
	}
}

 

V metóde insertionSort budeme postupne vytvárať triediaci algoritmus od základov až do úplného dokončenia. To znamená, že všetky nižšie rozpísané fázy obsahujú úryvky kódu, ktorý budeme vkladať do tejto metódy. Postup rozdelíme do dvoch fáz ab, ktoré budú korešpondovať s bodmi [A][B] z opisu na začiatku článku.

Poznámka: Jednoduchšie z triediacich algoritmov (bublinkové, vkladaním, výberom…) obsahujú dvojitý cyklus – dva cykly, z ktorých jeden je vnorený do druhého. Hovoríme aj, že algoritmus má vonkajšívnútorný cyklus. Fáza a v tomto príklade korešponduje s vonkajším cyklom. Fáza b zase s vnútorným.

 

Vonkajší cyklus definujeme s pomocou riadiacej štruktúry cyklu s explicitným počtom opakovaní – for. Začíname opakovanie od indexu jeden (pretože, ako bolo povedané, nultý prvok nemá zmysel posúvať viac doľava).

~

// To znamená, že „ukazovateľom“ z opisu na začiatku článku je premenná i.
for (int i = 1; i < pole.length; ++i)
{
	// Tu budeme pokračovať ďalším krokom.
}

Týmto cyklom je zároveň naplnená posledná odrážka zoznamu z opisu algoritmu na začiatku článku – „ak je to možné (ak sa dá posúvať doprava)…“ – vonkajší cyklus bude posúvať ukazovateľ (premennú i) len do hornej hranice poľa (do dĺžky poľa) a bude sa vykonávať len dovtedy, kým bude toto posúvanie možné.

(Prejdite do fázy a2.)

Do tela cyklu začneme vpisovať príkazy plniace bod [A].

~

// V súlade s opisom na začiatku článku (pri bode [A]) vykonáme:

// Nastavenie aktuálnej pozície na hodnotu ukazovateľa –
// takže aktuálnu pozíciu bude uchovávať premenná j:
int j = i;

// Vloženie aktuálneho prvku do pomocnej premennej (pomenovali sme ju „prvok“):
int prvok = pole[j];

// Tu budeme pokračovať ďalším krokom.

(Prejdite do fázy b1.)

V tomto kroku začneme tvoriť vnútorný cyklus, ktorý bude tvoriť krok [B].

~

// Podmienky vnútorného cyklu musia pred každým vykonaním overiť, či je:
//
//   1. aktuálna pozícia (index j) vyššia od nuly, pretože keď
//      sa dostaneme do pozície s indexom rovným nule, tak už sa nie
//      je možné posúvať viac doľava,
//
//   2. hodnota prvku naľavo od aktuálnej pozície väčšia ako hodnota
//      uložená v pomocnej premennej (v súlade s opisom na začiatku
//      článku):
//
while (j > 0 && pole[j - 1] > prvok)
{
	// Tu budeme pokračovať ďalším krokom.
}

// Sem vložíme posledný príkaz z fázy a3.

(Prejdite do fázy b2.)

V tomto kroku dokončíme vnútorný cyklus – naplníme jeho telo príkazmi. (Ide o dokončenie bodu [B].)

~

// Hlavnou činnosťou v tele vnútorného cyklu je presunutie (skopírovanie)
// prvku zľava od aktuálnej pozície na aktuálnu pozíciu:
pole[j] = pole[j - 1];

// Ďalšou činnosťou je posunutie aktuálnej pozície doľava:
--j;

(Prejdite do fázy a3.)

Posledným krokom je príkaz, ktorý umiestnime za telo vnútorného cyklu a ktorým tvorbu algoritmu dokončíme. Ide o splnenie predposlednej odrážky z opisu algoritmu na začiatku článku – „vložím hodnotu pomocnej premennej na aktuálnu pozíciu“:

~

pole[j] = prvok;

(Zobrazte výsledok.)

Toto je výsledný algoritmus:

~

for (int i = 1; i < pole.length; ++i)
{
	int j = i;
	int prvok = pole[j];

	while (j > 0 && pole[j - 1] > prvok)
	{
		pole[j] = pole[j - 1];
		--j;
	}

	pole[j] = prvok;
}

Keď sa na neho pozrieme, zistíme, že by bolo vhodné ho mierne optimalizovať. Výpočet j - 1, ktorý sa nachádza v podmienkach vnútorného cyklu sa dá odstrániť. Síce na úkor toho vzniknú dva iné výpočty, ale keďže cyklus sa má šancu zopakovať viac než len dva razy (a často sa aj zopakuje viac než dva razy), tak tým celkovo získame.

Bude to vyžadovať úpravy na viacerých riadkoch – hodnotu pomocnej premennej už nebudeme napĺňať s pomocou indexu j, ale s pomocou indexu i, čo neprekáža, lebo pôvodne mali rovnaké hodnoty. Teraz bude index j ukazovať na pozíciu vľavo od aktuálnej, čo bude mať za následok:

  • zmenu podmienok vnútorného cyklu,
  • zmenu príkazu na posúvanie prvkov doprava (prvý príkaz v tele vnútorného cyklu)
  • a zmenu príkazu na vloženie prvku na aktuálnu pozíciu (za telom vnútorného cyklu).

Toto je prepísaný algoritmus:

~

for (int i = 1; i < pole.length; ++i)
{
	int prvok = pole[i];

	int j = i - 1;
	while (j >= 0 && pole[j] > prvok)
	{
		pole[j + 1] = pole[j];
		--j;
	}

	pole[j + 1] = prvok;
}

Pri poslednom príkaze je dobré upozorniť na to, že nesmieme namiesto výpočtu j + 1 použiť premennú i. Pre skúsenejších programátorov ide o jasnú vec, na ktorú netreba upozorňovať (aj keď niekedy sa i skúsenejší môže zmýliť). Menej skúsených, prípadne momentálne menej pozorných, môže v honbe za ďalším zefektívnením táto zámena zlákať. Treba si však uvedomiť, že hodnota premennej j (t. j. „aktuálnej pozície“) už môže byť (a často aj je) po skončení vykonávania vnútorného cyklu posunutá omnoho viac doľava než hodnota premennej i (t. j. „ukazovateľa“).