Insertion sort je algoritmus řazení (řazení vkládáním), který je poměrně pomalý. Jeho asymptonická složitost je O(n²). Přesto dosahuje mnohem lepších výsledků, než jiné algoritmy s kvadratickou složitostí (například bubble sort nebo selection sort). V nejideálnějších případech může dosahovat i lineárního času a v řazení malé množiny čísel (přibližně do 15 hodnot) může být rychlejší než quicksort.
Má velice snadnou implementaci a jelikož je velice efektivní v malých množinách, tak je dobré ho v jistých případech použít (někdy je prostě zbytečné používat quicksort nebo merge sort).
Ukázka, jak insertion sort pracuje.
Ještě jedna animace demonstrující insertion sort.
Implementace do Javy:
Napíšeme si jednoduchou statickou metodu, která nám bude řadit pole celých čísel. Metodu pojmenujeme insertion() a jejím vstupním parametrem bude pole celých čísel s názvem pole.
public static void insertion(int[] pole) {
for(int i = 1;i < pole.length;i++) {
int j = i;
int tmp = pole[i];
while(j > 0 && pole[j-1]>tmp) {
pole[j] = pole[j-1];
j--;
}
pole[j] = tmp;
}
}
Další užitečné informace o tomto algoritmu - en.wikipedia.org.
