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 ²⁾ a začína zaostávať za algoritmy múdrejšími.

Vlastnosti algoritmu

časová zložitosť	O (n ²⁾
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:

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

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

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

Pôjdeme zatriediť ďalší prvok, ktorým je teraz prvok 5.

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.

Pamäť: 1

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.

Posledný je prvok 4, začneme teda s posúvaním.

Pamäť: 4

Zastavíme sa pred prvkom 3 a vložíme prvok 4 z pamäte na voľné miesto. Hotovo

Vizualizácia

Video ukážka

Zdrojový kód

Java
C #
Delphi
Ruby

public static void 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;
  }
}

public static void 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 - 1
    while ((j >= 0) && (list[j] > item))
      list[j + 1] = list[j]
      j -= 1;
    end
    list[j + 1] = item
  end
end

Článok pre vás napísal David Hartinger

Užívateľské hodnotenie:

Ešte nikto nehodnotil, buď prvý!

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.

Aktivity