Algorytmy, struktury danych i techniki programowania. Wydanie V
49,00 zł
Zrozum struktury danych. Algorytmy i praca na danych w Javie
−30%27,93 zł
Opus magnum C++11. Programowanie w języku C++ (komplet)
149,00 zł
Kwalifikacja EE.08. Montaż i eksploatacja systemów komputerowych, urządzeń peryferyjnych i sieci. Część 2. Systemy operacyjne. Podręcznik do nauki zawodu technik informatyk
37,95 zł
Kwalifikacja E.12. Montaż i eksploatacja komputerów osobistych oraz urządzeń peryferyjnych. Podręcznik do nauki zawodu technik informatyk
57,00 zł
Kwalifikacja E.14. Część 3. Tworzenie aplikacji internetowych. Podręcznik do nauki zawodu technik informatyk
37,95 zł

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 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: 0.

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

Zobacz też

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

Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.

Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.

Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).

Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).

→ Czytaj całość

Algorytm genetycznymetaheurystyka inspirowana 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