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í . 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í , tak se u téměř seřazeného pole jeho složitost blíží k
– 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
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
(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;