Sortowanie przez wstawianie

Małgorzata Piekarska

Proste wstawianie

Wstęp

Sortowanie przez wstawianie (funkcjonuje też nazwa umieszczanie) jest metodą porządkowania zbioru o złożoności kwadratowej. Żeby zrozumieć istotę jego działania wystarczy uzmysłowić sobie sposób, w jaki szeregujemy karty w dłoni (każdą kolejną kartę wstawiamy w odpowiednie miejsce w wachlarzu posortowanych kart). Porównując ten algorytm z bąbelkowym można go nazwać bardziej inteligentnym, gdyż ilość operacji jest zależna od ułożenia wartości w ciągu na wejściu (jest bardziej wydajny dla danych wstępnie posortowanych).

Zasada działania

W algorytmie sortowania przez wstawianie ciąg danych jest niejako sztucznie podzielony na dwie części: uporządkowaną (przed rozpoczęciem działania algorytmu ta część zawiera jeden element), nieuporządkowaną (zawiera wszystkie pozostałe elementy).

Sposób porządkowania można w skrócie opisać następująco:
- pobierz pierwszą z brzegu wartość z części nieuporządkowanej (jeśli ta część jest pusta to zakończ działanie algorytmu),
- wstaw ją we właściwe miejsce pomiędzy elementy z części posortowanej (po takiej operacji część nieuporządkowana jest jeden element krótsza, a część posortowana jeden element zyskuje).

Pozostaje jedynie do rozstrzygnięcia, w jaki sposób technicznie wyznaczyć właściwe miejsce nowej wartości w części uporządkowanej.
Najprościej zrobić to porównując wartość elementu wstawianego z kolejnymi elementami w części wcześniej uporządkowanej (począwszy od ostatniego). Jeżeli element na pozycji i jest większy bądź równy wstawianemu, to ten nowy element należy umieścić tuż za nim.

Implementacja

    for (int i = 1; i < n; i++)   //a[0] stanowi jednoelementowy ciąg posortowany  
    {
        taken= a[i]; //pierwszy z brzegu zostaje pobrany do umieszczenia
        int k=i-1;
        while( k>=0 && a[k] > taken) 
          {
            a[k + 1] = a[k]; //przesuwamy wszystkie o 1 w prawo robiąc miejsce dla umieszczenia nowego
            k--;
          }
        a[k+1] = taken; //umieszczenie wartości we właściwym miejscu
    }

Binarne wstawianie

Ta metoda różni się od opisanej powyżej, strategią wstawiania elementu do ciągu uporządkowanego. Wykorzystuje się tu umieszczanie binarne, to znaczy miejsce, w które mamy wstawić element wyznacza się tu za pomocą wyszukiwania binarnego.
Analizując złożoność tego sposobu, można by dojść do mylnego wniosku, że mamy teraz do czynienia ze złożonością O(nlogn), jednakże należy zauważyć, że zmniejszyliśmy jedynie ilość porównań, a nie przesunięć. Nadal przy wstawianiu elementu w wyszukane miejsce musimy przesunąć w prawo wszystkie kolejne wartości by zrobić miejsce dla umieszczonego. Tak więc złożoność pozostaje kwadratowa (operacją wiodącą nie jest tu bowiem samo odszukanie pozycji dla wstawienia elementu). Co więcej, w przypadku gdy mamy do czynienie z ciągiem posortowanym, sposób ten może okazać się wolniejszy niż proste wstawianie.