Sortowanie przez scalanie

Sortowanie przez scalanie (1) Przykład sortowania przez scalanie
Scalanie (2) Operacja scalania

Sortowanie przez scalanie – rekurencyjny algorytm sortowania wykorzystujący metodę dziel i zwyciężaj.

Działanie algorytmu

Sortowanie przez scalanie przebiega następująco:

  • Jeśli rozmiar tablicy do posortowania wynosi 1, nic nie rób (tablica jest już posortowana).
  • W przeciwnym razie:
    • Posortuj pierwszą połowę tablicy.
    • Posortuj drugą połowę tablicy.
    • Scal otrzymane wyniki.

Operacja scalania polega na porównywaniu pierwszych elementów posortowanych podtablic i przenoszeniu mniejszego z nich (lub większego, jeśli sortujemy malejąco) do nowej tablicy. Jeśli w jednej z podtablic nie ma już elementów, trzeba kolejno przenosić do tablicy z wynikami kolejne elementy drugiej.

Złożoność obliczeniowa

Głębokość drzewa wywołań funkcji dla tablicy o rozmiarze n wynosi log2n (zaokrąglone w górę). Złożoność operacji scalania tablic jest liniowa. Złożoność czasowa algorytmu jest zatem O(nlogn).

W pamięci operacyjnej potrzebne jest miejsce na obsługę kolejnych wywołań funkcji oraz na tymczasowe tablice potrzebne przy scalaniu. Złożoność pamięciowa algorytmu jest rzędu O(n).

Ocena algorytmu

Algorytm ma mniejszą złożoność czasową niż proste algorytmy, takie jak np. sortowanie bąbelkowe czy sortowanie przez wstawianie. W zamian za to ma jednak gorszą złożoność pamięciową.

Dodatkową zaletą sortowania przez scalanie jest to, że algorytm ten można zrównoleglić. Poszczególne podtablice można sortować niezależnie od siebie, zatem sortowania te można wykonywać w osobnych wątkach.

Przykładowa implementacja w języku C++

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

void sortowanie_przez_scalanie(int* tab, int n)
{
    if (n > 1) 
    {
        int n1 = n/2;
        int n2 = n - n1;
        
        // Wywolanie rekurencyjne
        sortowanie_przez_scalanie(tab, n1);  
        sortowanie_przez_scalanie(&tab[n1], n2);
    
        //Przepisanie wynikow do tymczasowych tablic
        int i;
        
        int* tab1 = new int[n1];
        int* tab2 = new int[n2];

        for (i = 0; i < n1; ++i)
        {
            tab1[i] = tab[i];
        } 
        for (i = n1; i < n; ++i)
        {
            tab2[i-n1] = tab[i];
        }
    
        // Scalenie
        int in1, in2;
        in1 = in2 = 0;
        
        for (i = 0; i < n; ++i) 
        {
            if ((in1 < n1) && (tab1[in1] <= tab2[in2]))
            {
                tab[i] = tab1[in1];
                ++in1;
            }
            else
            {
                tab[i] = tab2[in2];
                ++in2;
            }                     
        }
    
        delete[] tab1;
        delete[] tab2;
    }
}

Bibliografia

  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Ocena: -6 Tak Nie
Liczba głosów: 10.

Dodano: 29 czerwca 2017 14:33, ostatnia edycja: 30 stycznia 2019 15:50.

REKLAMA

Zobacz też

Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.

W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:

Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:

Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.

Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.

→ Czytaj całość

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ 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ść
Polityka prywatnościKontakt