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:

  1. Mějmě jeden prvek, ten je triviálně seřazen.
  2. 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.)
  3. 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;
 







Doporučujeme