Funkce, kterou se snažíš použít je dostupná pouze pro registrované uživatele. Buďto se přihlas nebo si zdarma vytvoř nový účet.
Triedenie priamym vkladaním
Triedenie priamym vkladaním je kráľom medzi jednoduchými triediacimi
algoritmy. Je stabilný, jednoduchý na implementáciu, chová sa inteligentne
na už predtriedených poliach a na malých poliach (rádovo desiatky prvkov)
vďaka svojej jednoduchosti predbehne aj Quicksort.
Triedenie priamym vkladaním vidí poľa rozdelenej na 2 časti - zotriedenú
a Hlavička. Postupne vyberá prvky z Netriediť časti a vkladá je
medzi prvkami v zotriedené časti tak, aby zostala zotriedená. Od
toho jeho meno - vkladá prvok presne tam, kam patrí a nerobí teda žiadne
zbytočné kroky, ako napríklad Bubble sort.
Na väčších poliach sa samozrejme začne prejavovať handicap algoritmu,
ktorý spočíva v jeho časovej zložitosti O (n 2) a začína
zaostávať za algoritmy múdrejšími.
Vlastnosti algoritmu
časová zložitosť
O (n 2)
stabilita
áno
rýchlosť
Vysoká na malých poliach
Pozn. je myslená časová zložitosť priemerného prípadu a rýchlosť
vzhľadom ku všetkým triediacim algoritmom
Priebeh
Máme pole nasledujúcich prvkov:
3
2
5
1
9
4
Prvý prvok (3) budeme považovať za klasifikované a zvyšok poľa za
nesedtříděný. Začneme teda od druhého prvku (2), ktorý si uložíme do
pomocnej pamäte.
Pamäť: 2
3
2
5
1
9
4
Teraz budeme vytvárať miesto pre tento prvok v už zotriedené časti, kam ho
potom vložíme. Budeme posúvať prvky v zotriedené časti poľa doprava tak
dlho, kým buď nenarazíme na prvok menšie (alebo rovnaký) alebo na začiatok
poľa. Trochu mätúce môže byť, že jeden prvok bude v poli fyzicky
zapísaný 2x, pretože raz to bude znamenať medzeru (vyznačené šedou
farbou). Z teoretického hľadiska je tam prázdno, ako môžete vidieť ďalej
na demonštrácii algoritmu na videu.
Späť k nášmu prípadu - v pamäti máme prvok 2, ktorý je určite
menší ako prvok 3, preto prvok 3 posunieme doprava. Tým sa pripravíme o
prvok 2, ale ten máme v pamäti, takže nám to nijako nevadí.
Pamäť: 2
3
3
5
1
9
4
Pred vzniknutú medzerou je už začiatok poľa, vložíme teda na "prázdne"
miesto prvok z pamäte. Zotriedená časť poľa má už teda 2 prvky.
Pamäť: 2
2
3
5
1
9
4
Pôjdeme zatriediť ďalší prvok, ktorým je teraz prvok 5.
2
3
5
1
9
4
Zistíme, že je pred ním menšie číslo, je teda na správnom mieste.
Veľkosť zotriedené časti sa opäť zväčší. Ďalším na rade bude prvok
1.
2
3
5
1
9
4
Pamäť: 1
2
3
5
5
9
4
Pamäť: 1
2
3
3
5
9
4
Pamäť: 1
2
2
3
5
9
4
Pamäť: 1
1
2
3
5
9
4
Zarazil nás až začiatok poľa, pretože žiadny iný prvok nebol menší ako
jednička. Prvok 9 očividne zostane na mieste.
1
2
3
5
9
4
Posledný je prvok 4, začneme teda s posúvaním.
1
2
3
5
9
4
Pamäť: 4
1
2
3
5
9
9
Pamäť: 4
1
2
3
5
5
9
Zastavíme sa pred prvkom 3 a vložíme prvok 4 z pamäte na voľné miesto.
Hotovo
publicstaticvoid insertionSort(int[] list) {
int item, j;
for (int i = 1; i <= (list.length - 1); i++) {
// ulozeni prvku
item = list[i];
j = i - 1;
while ((j >= 0) && (list[j] > item)) {
list[j + 1] = list[j];
j--;
}
list[j + 1] = item;
}
}
publicstaticvoid insertionSort(int[] list) {
int item, j;
for (int i = 1; i <= (list.Length - 1); i++) {
// ulozeni prvku
item = list[i];
j = i - 1;
while ((j >= 0) && (list[j] > item)) {
list[j + 1] = list[j];
j--;
}
list[j + 1] = item;
}
}
// setridi vlozene pole, predpoklada indexovani od 0
procedure insertion_sort(var list: array of integer)
var i, j, item: integer;
begin
for i:=1 to (length(list) - 1) do begin
// ulozeni prvku
item:=list[i];
j:=i - 1;
while ((j >= 0) and (list[j] > item)) do begin
list[j + 1]:=list[j];
dec(j);
end;
list[j + 1]:=item;
end;
end;
def insertion_sort(list)
1.upto(list.length - 1) do |i|
# ulozeni prvku
item = list[i]
j = i - 1while ((j >= 0) && (list[j] > item))
list[j + 1] = list[j]
j -= 1;
end
list[j + 1] = item
end
end
David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.