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: +9 Tak Nie
Liczba głosów: 19.

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

REKLAMA

Zobacz też

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

→ 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ść

Algorytm genetyczny – jedna z metaheurystyk inspirowanych biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość
Polityka prywatnościKontakt