Programowanie w języku C/C++ » FAQ

Insertion Sort

  • 2010-10-31 18:27
  • 1 komentarz
  • 6417 odsłon
  • Oceń ten tekst jako pierwszy
Sortowanie przez wstawianie (insertion sort) jest naturalnym algorytmem sortowania. Wielu ludzi stosuje go często, nawet o tym nie wiedząc, chociażby przy układaniu kart w ręce. Sortowanie to jest stabilne, in situ, o złożoności średniej O(n^2). Jest uznawane za najszybsze z sortowań prostych, dodatkowo jest bardzo intuicyjne i nieskomplikowane w implementacji. Nadaj się również do sortowania list. Czasem używa się go w sortowaniu szybkim do sortowania odpowiednio małych przedziałów, co korzystnie wpływa na czas tej operacji.

Sortowanie przez wstawianie (insertion sort) jest stabilnym algorytmem sortowania w miejscu, o kwadratowej złożoności czasowej. Głowne jego zalety to naturalne zachowanie, prostota implementacji i bardzo dobre wyniki dla małych danych wejściowych.

Opis algorytmu


Daną jest tablica, o długości n, oznaczmy: [0, n - 1].

Algorytm ten jest iteracyjny. Zacznijmy od i = 1.
Na początku każdego (i-tego) przebiegu pętli (niezmiennik pętli) mamy tablicę podzieloną na dwie części - posortowaną i nieposortowaną : [0, i - 1], [i, n - 1].
W każdej iteracji wstawiamy pierwszy element z części nieposortowanej, do części posortowanej w odpowiednim miejscu, co powoduje przesunięcie granicy podziału o 1: [0, i], [i + 1, n - 1] (zachowanie niezmiennika).
Jak widać, wystarczy iterować tą pętle dla i od 1 do n, aby cała tablica była posortowana.


Pseudokod


  1. procedure insertion_sort(array A)
  2. begin
  3.   for I ← 1 to A.size do
  4.   begin
  5.     integer J ← I
  6.     while J > 0 and A[J] < A[J - 1] do
  7.     begin
  8.       A[J] ←→ A[J - 1]
  9.       J ← J - 1
 10      end
 11    end
 12. end


6. Dopóki I-ty element nie znajduje się na odpowiednim miejscu, zamieniamy go z sąsiadującym elementem, który jest większy od niego. W tym miejscu korzystamy z faktu, że część tablicy od 0 do I - 1 jest posortowana.

Można by pomyśleć, że efektywność tego algorytmu wzrosłaby, gdyby zastosować wyszukiwanie połówkowe, do znalezienia docelowej pozycji dla danego elementu, jednak nie jest to zbyt dobry pomysł, bo i tak musimy przestawić wszystkie elementy, które znajdują się między danym elementem, a miejscem, gdzie powinien się znaleźć.
Dużo lepszą i bardziej ciekawą modyfikacją tego algorytmu jest shell sort, który z drobnymi modyfikacjami może mieć średnią złożoność nawet rzędu O(n lg^2 n).

Implementacja (C/C++)


void insertion_sort(int *tab, int n){
    int i, j, el; 
    for ( i = 1; i < n; ++i ){
        el = tab[i];
        for ( j = i; j > 0 && tab[j - 1] > el; j-- )
            tab[j] = tab[j - 1];
    }
}


Implementacje (Python)


Według opisu algorytmu:

def insertion_sort1(tab):
    for i in range(len(tab)):
        assert tab[0:i]==sorted(tab[0:i]), 'Naruszenie niezmiennika petli'
        j = i
        while j > 0 and tab[j] < tab[j-1]:
            tab[j], tab[j-1] = tab[j-1], tab[j]
            j -= 1


Ponieważ mamy zapewnione, że część tablicy 0:i jest posortowana, możemy przyspieszyć wyszukiwanie miejsca do wstawienia elementu wykorzystując metodę bisekcji i wstawić od razu we właściwe miejsce, zmniejszając liczbę przestawień.

from bisect import insort
def insertion_sort2(tab):
    for i in range(len(tab)):
        assert tab[0:i]==sorted(tab[0:i]), 'Naruszenie niezmiennika petli'
        tmp = tab.pop(i)
        insort(tab, tmp, 0, i)


 

1 komentarz

Slepy_Bart 2009-03-11 13:09

W przykładzie napisanym w c++ zabrakło ważnej rzeczy.

for ( j = i; j > 0 && tab[j - 1] > el; j-- ){
            tab[j] = tab[j - 1];
            tab[j-1] = el;
}


Tak jak widać teraz liczba poprzednia w przypadku gdy była mniejsza od następnika zostawała usuwana. Nie wiem jak w innych przykładach bo tylko ten język znam.