Sortowanie przez scalanie – rekurencyjny algorytm sortowania wykorzystujący metodę dziel i zwyciężaj.
Sortowanie przez scalanie przebiega następująco:
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.
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).
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ł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; } }
Dodano: 29 czerwca 2017 14:33, ostatnia edycja: 30 stycznia 2019 15:50.
Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.
Algorytm genetyczny – metaheurystyka 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.
Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.
Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.