Sortowanie przez wstawianie

Tutorial
Na ten temat mamy również tutorial „Sortowanie przez wstawianie”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
Sortowanie przez wstawianie (1) Przykład sortowania przez wstawianie

Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.

Działanie algorytmu

Sortowany ciąg dzielony jest na część posortowaną i nieposortowaną. Na początku w części posortowanej znajduje się tylko jeden element (pierwszy). W każdym kolejnym kroku bierzemy pierwszy element z części nieposortowanej i wstawiamy we właściwe miejsce części posortowanej. Aby to zrobić, wstawiany element porównujemy kolejno z ostatnim elementem posortowanej części ciągu, z przedostatnim itd. Algorytm kończy się, gdy wszystkie elementy znajdują się w części posortowanej.

Przykładowy kod źródłowy w języku C jest umieszczony poniżej. Kod ten realizuje sortowanie rosnące.

void sortowanie_przez_wstawianie(int* tab, int n)
{
    int i, j, t;

    for (i = 1; i < n; ++i)
    {
        j = i;
        while ( (j > 0) && (tab[j-1] > tab[j]) ) 
        {
            t = tab[j];
            tab[j] = tab[j-1];
            tab[j-1] = t;
            --j;
        } 
    } 
}

Złożoność czasowa

Główna pętla algorytmu wykona się n-1 razy (n jest liczbą elementów do posortowania). W każdym wykonaniu pętli głównej wystąpi od 1 do j porównań, gdzie j jest numerem aktualnego wykonania pętli. W przypadku pesymistycznym algorytm wykona 1+…+(n-1)+(n-2)=(n-1)*n/2 porównań, czyli tyle samo, co algorytm sortowania bąbelkowego. Jednak w przypadku optymistycznym (sortowanie posortowanego ciągu) w każdym wykonaniu pętli głównej odbędzie się tylko jedno porównanie, co daje łącznie jedynie n-1 porównań (złożoność optymistyczna jest zatem liniowa).

Policzmy teraz, jaka jest średnia złożoność algorytmu. Jak już wspomniano, w każdym wykonaniu pętli głównej wystąpi od 1 do j porównań. Zakładając, że każda z tych liczb jest tak samo prawdopodobna, średnia liczba porównań wynosi (j+1)/2. W całym algorytmie wystąpi zatem (1+1)/2+(2+1)/2+…+n/2 porównań, czyli (n-1)(n+2)/4. Nadal jest to złożoność kwadratowa, jednak jest to algorytm szybszy od sortowania bąbelkowego. Przewaga sortowania przez proste wstawianie będzie tym większa, im większe będzie prawdopodobieństwo, że elementy w ciągu już na początku są częściowo posortowane.

Ocena: 0 Tak Nie
Liczba głosów: 4.

Dodano: 29 września 2016 11:53, ostatnia edycja: 28 czerwca 2017 15:19.

REKLAMA

Zobacz też

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.

→ Czytaj całość

Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.

→ Czytaj całość
Polityka prywatnościKontakt