Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie (ang. Insertion Sort) to prosty algorytm sortowania, który działa na zasadzie porównywania i wstawiania elementów do odpowiednich miejsc, podobnie jak w przypadku układania kart. Jest szczególnie efektywny dla małych zbiorów danych, chociaż jego złożoność wynosi $O(n^2)$. Mimo niższej wydajności w porównaniu do algorytmów takich jak quicksort czy heapsort, sortowanie przez wstawianie ma kilka istotnych zalet:

• Liczba porównań jest zależna od inwersji w danych, co czyni go wydajnym dla zbiorów wstępnie posortowanych.
• Efektywność w przypadku małych zbiorów danych.
• Stabilność algorytmu.

Można zastosować modyfikację algorytmu, wykorzystując wyszukiwanie binarne, co zmniejsza liczbę porównań do $O(n\; \backslash log\; n)$, jednak liczba przesunięć elementów pozostaje na poziomie $O(n^2)$.

Schemat działania algorytmu

Algorytm działa według następującego schematu:

1. Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element z zbioru nieposortowanego.
2. Weź dowolny element ze zbioru nieposortowanego.
3. Porównuj wyciągnięty element z kolejnymi elementami zbioru posortowanego, aż znajdziesz element równy lub większy (dla ciągu niemalejącego) lub dotrzesz do początku/końca zbioru.
4. Wstaw wyciągnięty element w odpowiednie miejsce.
5. Powtarzaj proces, aż zbiór nieuporządkowany stanie się pusty.

Pseudokod algorytmu

Poniższy pseudokod ilustruje algorytm:

Insert_sort(A, n):
for i=2 to n:
# Wstaw A[i] w posortowany ciąg A[1 … i-1]
wstawiany_element = A[i]
j = i – 1
while j > 0 and A[j] > wstawiany_element:
A[j + 1] = A[j]
j = j – 1
A[j + 1] = wstawiany_element

Przykłady implementacji

Przykładowe implementacje sortowania przez wstawianie można znaleźć na Wikibooks.