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

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

REKLAMA

Zobacz też

Algorytm heurystyczny, heurystyka – algorytm poszukujący najlepszego spośród wielu dostępnych rozwiązań. Algorytmy heurystyczne w ogólnym przypadku nie dają gwarancji znalezienia rozwiązania optymalnego, jednak pozwalają znaleźć rozwiązanie dość dobre w stosunkowo krótkim czasie.

Pojęcie algorytmów heurystycznych jest bardzo szerokie, dotyczy ono różnych technik projektowania algorytmów. Wiele heurystyk wykorzystuje losowość, inne zaś są deterministyczne (wówczas dla takich samych danych wejściowych algorytm zawsze zwróci ten sam wynik).

Ogólny algorytm heurystyczny (opisujący samą ideę poszukiwań) bywa określany w literaturze jako metaheurystyka. Zgodnie z tym nazewnictwem, metaheurystyką jest np. algorytm zachłanny (jako ogólna idea), zaś heurystyką jest np. algorytm najbliższego sąsiada (jako zastosowanie idei algorytmu zachłannego do konkretnego problemu).

→ Czytaj całość

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

→ Czytaj całość

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość
Polityka prywatnościKontakt