Sortowanie przez wstawianie

Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort) – jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty – kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe. Jest efektywny dla niewielkiej liczby elementów, jego złożoność wyrażona notacją wielkiego O wynosi $O(n^{2})$. Pomimo tego, że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort, posiada pewne zalety:

• liczba wykonanych porównań jest zależna od liczby inwersji w permutacji, dlatego algorytm jest wydajny dla danych wstępnie posortowanych,
• jest wydajny dla zbiorów o niewielkiej liczebności,
• jest stabilny.

Sortowanie przez wstawianie

Przykład działania sortowania przez wstawianie
Rodzaj	Sortowanie
Struktura danych	Tablica, lista
Złożoność
Czasowa	$O(n^{2})$
Pamięciowa	$O(1)$

Istnieje modyfikacja algorytmu, pozwalająca zmniejszyć liczbę porównań. Zamiast za każdym razem iterować po już posortowanym fragmencie (etap wstawiania elementu), można posłużyć się wyszukiwaniem binarnym. Pozwala to zmniejszyć liczbę porównań do $O(n\log n)$, nie zmienia się jednak złożoność algorytmu, ponieważ liczba przesunięć elementów to nadal $O(n^{2})$.

Schemat działania algorytmu

Przykład działania

1. Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
2. Weź dowolny element ze zbioru nieposortowanego.
3. Wyciągnięty element porównuj z kolejnymi elementami zbioru posortowanego, póki nie napotkasz elementu równego lub elementu większego (jeśli chcemy otrzymać ciąg niemalejący) lub nie znajdziemy się na początku/końcu zbioru uporządkowanego.
4. Wyciągnięty element wstaw w miejsce, gdzie skończyłeś porównywać.
5. Jeśli zbiór elementów nieuporządkowanych jest niepusty, wróć do punktu 2.

Algorytm – pseudokod

Poniższy kod przedstawia algorytm zapisany w pseudokodzie, gdzie:

• A – tablica danych przeznaczonych do posortowania (indeksowana od 1 do n),
• n – liczba elementów w tablicy A.

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

• Zobacz przykładowe implementacje sortowania przez wstawianie na Wikibooks

Zobacz też

• Sortowanie Shella
• Sortowanie przez wybieranie

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.

Linki zewnętrzne

• Algorytm przedstawiony z wykorzystaniem rumuńskiego tańca