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.