Triedenie vkladaním
Triedenie vkladaním je interaktívny pokus z aplikácie Algoritmy v akcii, bezplatnej simulácie zo StudyFi Lab, ktorá beží priamo v prehliadači.
Triedenie vkladaním funguje ako triedenie kariet v ruke: ľavá časť je už zoradená a každý ďalší prvok (key) posúvaš doľava, kým nenarazíš na menší. Väčšie prvky sa pritom posunú o miesto doprava. Na náhodných dátach je to O(n²), ale na takmer zoradených skoro O(n) — zoradené pole potrebuje len n−1 porovnaní.
Vyskúšaj: Spusti ho na takmer zoradenom poli a potom na obrátenom. Koľkokrát viac posunov potrebuje obrátené pole?
Časté otázky
Čo ukazuje pokus „Triedenie vkladaním“?
Triedenie vkladaním funguje ako triedenie kariet v ruke: ľavá časť je už zoradená a každý ďalší prvok (key) posúvaš doľava, kým nenarazíš na menší. Väčšie prvky sa pritom posunú o miesto doprava. Na náhodných dátach je to O(n²), ale na takmer zoradených skoro O(n) — zoradené pole potrebuje len n−1 porovnaní.
Ako si vyskúšať „Triedenie vkladaním“?
Spusti ho na takmer zoradenom poli a potom na obrátenom. Koľkokrát viac posunov potrebuje obrátené pole?
Učíš sa na test?
Nahraj svoje poznámky a StudyFi z nich urobí kartičky, testy a podcasty.