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

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

REKLAMA

Zobacz też

Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.

Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.

→ Czytaj całość

Drzewo decyzyjne – metoda graficzna wspierająca podejmowanie decyzji, jak również model stosowany w uczeniu maszynowym do klasyfikacji lub regresji.

Podejmowanie decyzji z wykorzystaniem drzewa decyzyjnego odbywa się poprzez odpowiadanie na kolejne pytania. Pojedyncze pytanie musi być proste i dotyczyć jednego konkretnego atrybutu. Pytania ułożone są w strukturę hierarchiczną – wybór następnego pytania (lub końcowej decyzji) zależy od odpowiedzi udzielonej na poprzednie.

Proste drzewo decyzyjne może być w pełni zaprojektowane już przy tworzeniu programu i zaimplementowane w kodzie np. za pomocą instrukcji warunkowych. W uczeniu maszynowym drzewo jest generowane automatycznie na podstawie próbek ze zbioru uczącego.

→ Czytaj całość
Sortowanie bąbelkowe (ang. bubble sort) – prosty algorytm sortowania polegający na porównywaniu za sobą sąsiednich elementów. Złożoności czasowa algorytmu wynosi O(n2).
→ Czytaj całość
Polityka prywatnościKontakt