Sortowanie przez wstawianie (insertion sort) to prosty algorytm sortowania, który działa podobnie do układania kart w ręce. Kolejne elementy są pobierane z nieposortowanej części i wstawiane w odpowiednie miejsce w części już posortowanej.
Zasada działania
Dla każdego elementu algorytm:
- zapamiętuje aktualny element,
- porównuje go z elementami znajdującymi się po lewej stronie,
- przesuwa większe elementy w prawo,
- wstawia aktualny element w odpowiednie miejsce.
Przykład
[4, 2, 5, 1]
[2, 4, 5, 1]
[2, 4, 5, 1]
[1, 2, 4, 5]
Złożoność
Sortowanie przez wstawianie ma złożoność:
- najlepszy przypadek: O(n), gdy dane są już prawie posortowane,
- średni przypadek: O(n²),
- najgorszy przypadek: O(n²).
Z tego powodu nie jest najlepszym wyborem dla bardzo dużych zbiorów danych.
Stabilność
Sortowanie przez wstawianie jest algorytmem stabilnym, jeśli przy porównywaniu nie przesuwa elementów równych względem siebie. Oznacza to, że elementy o tej samej wartości zachowują pierwotną kolejność.
Zastosowanie
Algorytm jest prosty do zrozumienia i dobrze działa dla małych lub prawie posortowanych tablic.