Insertion sort

Insertion sort (řazení vkládáním) je stabilní řadící algoritmus založený na principu porovnávání řazených hodnot se složitostí $O(n^{2})$ . Vylepšením Insertion sortu je výkonnější, ale nestabilní, Shell sort.

Princip

Insertion sort využívá tohoto myšlenkového postupu:

Mějmě jeden prvek, ten je triviálně seřazen.
Vezměme následující prvek a zařaďme jej na správné místo v již seřazených prvcích. (Tímto je nyní seřazeno o jeden prvek více než v předchozím kroku.)
Dokud pole obsahuje nezařazené prvky, tak GOTO: 2.

Výhody Insertion sortu

Ač se jedná o řazení se složitostí $O(n^{2})$ , tak se u téměř seřazeného pole jeho složitost blíží k O(n) – nedochází k posunům, pouze k průchodu. Díky k této výkonnostní výhodě je insertion sort a jeho modifikace často používán jako doplněk k řadícím algoritmům typu rozděl a panuj (quicksort, merge sort) pro řazení malých polí (pro $n \\leq 10$ je insertion sort rychlejší než quicksort).

Vizualizace

Příklad

(3 2 8 7 6) // Zadání, prvek 3 je triviálně seřazen
(3 2 8 7 6) // Vezmeme dvojku a vložíme jí na správné místo (tam už je)
(3 2 8 7 6) // 8 vložíme na první místo, zbytek čísel posuneme
(8 3 2 7 6) // 7 vložíme mezi 8 a 3, 3 a 2 posuneme
(8 7 3 2 6) // 6 vložíme mezi 7 a 3, čísla 3 a 2 posuneme
(8 7 6 3 2) // seřazeno

Kód

function insertionSort(array a)
    for i in 0 -> a.length - 2 do
        j = i + 1
        tmp = a[j]
        while j > 0 AND tmp > a[j-1] do //uvolni misto hodnote
            a[j] = a[j-1]
            j--
        a[j] = tmp //vloz hodnotu

/**
 * Razeni vkladanim (od nejvyssiho)
 * @param array pole k serazeni
 */
public static void insertionSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int j = i + 1;
        int tmp = array[j];
        while (j > 0 && tmp > array[j-1]) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = tmp;
    }
}

/**
 * Razeni vkladanim (od nejvyssiho)
 * @param array pole k serazeni
 * @param size velikost pole
 */
void insertionSort(int array[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int j = i + 1;
        int tmp = array[j];
        while (j > 0 && tmp > array[j-1]) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = tmp;
    }
}

/**
 * Razeni vkladanim (od nejvyssiho)
 * @param array pole k serazeni
 */
public static void InsertionSort(int[] array)
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        int j = i + 1;
        int tmp = array[j];
        while (j > 0 && tmp > array[j - 1])
        {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = tmp;
    }
}

procedure Insert(var X : ArrayType; N : integer);
var
  J,
  K,
  Y : integer;
  Found : boolean;
begin
  for J := 2 to N do
    begin
      Y := X[J];
      K := J - 1;
      Found := false;
      while (K >= 1)
      and (not Found) do
        if (Y < X[K]) then
          begin
            X[K + 1] := X[K];
            K := K - 1
          end
        else
          Found := true;
      X[K + 1] := Y;
    end
 end;

Princip

Výhody Insertion sortu

Vizualizace

Příklad

Kód

Doporučujeme