Sortowanie przez wstawianie

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)$

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.

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