Algorytmy, struktury danych i techniki programowania. Wydanie V
49,00 zł
JavaScript. Wyrażenia regularne dla programistów
−30%34,30 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ł
Hartowanie Linuksa we wrogich środowiskach sieciowych. Ochrona serwera od TLS po Tor
59,00 zł
Zajęcia rewalidacyjne. Zeszyt ćwiczeń dla szkoły podstawowej, klasy 4-6
14,90 zł

Sortowanie przez scalanie

Sortowanie przez scalanie Przykład sortowania przez scalanie
Scalanie 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

  1. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012.
Ocena: +1 Tak Nie
Liczba głosów: 1.

Dodano: 29 czerwca 2017 14:33, ostatnia edycja: 29 czerwca 2017 18:18.

Zobacz też

Problem komiwojażera (ang. travelling salesman problem, w skrócie TSP) – problem obliczeniowy polegający na poszukiwaniu w grafie takiego cyklu, który zawiera wszystkie wierzchołki (każdy dokładnie raz) i ma jak najmniejszy koszt. Bardziej formalnie, problem komiwojażera polega na poszukiwaniu w grafie cyklu Hammiltona o najmniejszej wadze.

Problem ma liczne zastosowania w życiu codziennym. Najlepszym przykładem jest praca kuriera, który musi wyjechać z magazynu, zawieźć przesyłki w różne miejsca i wrócić do magazynu.

Nie jest znany efektywny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia optymalnego rozwiązania problemu komiwojażera. Problem ten jest bowiem zaliczany do klasy problemów NP-trudnych. W wersji decyzyjnej (czy istnieje cykl o długości mniejszej od x) problem jest zaliczany do klasy problemów NP-zupełnych. W grafie pełnym mającym n wierzchołków liczba możliwych cykli Hammiltona wynosi aż (n-1)!/2. W praktyce sprawdzenie wszystkich możliwości jest zatem wykonalne tylko dla niewielkiej liczby wierzchołków.

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

Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.

→ Czytaj całość
Polityka prywatnościKontakt