INF.04Algorytmika i Struktury Danych
Sortowanie przez wstawianie (Insertion Sort)
Algorytm sortowania budujący posortowany ciąg element po elemencie poprzez wstawianie każdego nowego elementu na właściwą pozycję.
Zasada działania:
Działa podobnie jak układanie kart w dłoni. Bierzemy kolejny element z części nieposortowanej i wstawiamy go w odpowiednie miejsce w części już posortowanej, przesuwając większe elementy w prawo.
Złożoność:
- Optymistyczna: O(n) – gdy tablica jest już posortowana lub niemal posortowana!
- Średnia i pesymistyczna: O(n²).
- Pamięciowa: O(1) (w miejscu).
- Stabilność: Stabilny.
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Sortowanie przez wstawianie (Insertion Sort) lub rozpocznij trening.