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

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

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

Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.

Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.

Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.

Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.

→ Czytaj całość
Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, w skrócie NN) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną.
→ Czytaj całość
Polityka prywatnościKontakt