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).

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

Insertion sort - vizualizace

    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;

{ zpětná vazba }

Tweet		Delicious
Sdílet

Hodnocení (6): 4,08

Přečtěte si také

Diskuse

Článek zatím nemá žádné komentáře.