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.
Quicksort jest algorytmem rekurencyjnym, jego działanie można opisać następująco:
Wybór klucza osiowego może być dowolny, jednak powinien być jak najszybszy. W praktyce często stosuje się po prostu wybór pierwszego elementu.
Operacja przerzucania elementów powinna musi być zaimplementowana tak, aby wykonywała się w czasie liniowym. Przykładowo, może ona być zdefiniowana w następujący sposób:
Jak już wspomniano, operacja przenoszenia elementów odbywa się w czasie liniowym. O złożoności algorytmu decyduje więc to, ile nastąpi rekurencyjnych wywołań funkcji. W przypadku optymistycznym tablica będzie dzielona na pół. Wówczas głębokość drzewa wywołań zależy logarytmicznie od liczby danych wejściowych, czyli optymistyczna złożoność czasowa algorytmu jest rzędu O(n logn). Możemy wykazać, że taki sam rząd złożoności wystąpi w przypadku średnim (dowód jest dostępny w książkach podanych w bibliografii).
Przypadek pesymistyczny występuje wtedy, gdy klucz osiowy za każdym razem znajdzie się na brzegu tabeli. Wówczas przy każdym kolejnym wywołaniu liczba elementów do posortowania jest tylko o 1 mniejsza, zatem funkcja zostanie wywołana n razy. Pesymistyczna złożoność czasowa wynosi zatem O(n2).
Przeanalizujmy złożoność pamięciową algorytmu. Sortowanie szybkie nie potrzebuje co prawda dodatkowej pamięci na przechowywanie sortowanych danych, wymaga jednak pamięci potrzebnej na obsługę rekurencyjnych wywołań funkcji. Rozmiar tej pamięci (podobnie jak czas wykonania) będzie zależał od głębokości drzewa wywołań. Złożoność pamięciowa wynosi więc O(logn) w przypadku średnim i O(n) w przypadku pesymistycznym. Nie jest to zatem algorytm sortujący w miejscu.
Zastanówmy się, kiedy może wystąpić przypadek pesymistyczny. Jeśli jako klucz osiowy obieramy pierwszy (lub ostatni) elementu z tablicy, to najgorszy przypadek wystąpi wtedy, gdy tablica jest już posortowana. Widzimy więc, że algorytm zachowuje się w sposób bardzo nienaturalny.
Niedoskonałości algorytmu można nieco poprawić stosując następujące techniki:
Przykładowa implementacja algorytmu w języku C wygląda następująco:
void quicksort(int* tab, int poczatek, int n) { if (n > 1) { int liczba_mniejszych = 0; int liczba_wiekszych = 0; int koniec = poczatek + n; int t; // Zmienna tymczasowa // Przeniesienie elementow wokol klucza osiowego for (int i = (poczatek + 1); i < koniec; ++i) { if (tab[i] < tab[poczatek]) { if (liczba_wiekszych > 0) { // Przeniesienie elementu mniejszego od klucza osiowego // przed elementy wieksze od klucza osiowego t = tab[poczatek+liczba_mniejszych+1]; tab[poczatek+liczba_mniejszych+1] = tab[i]; tab[i] = t; } ++liczba_mniejszych; } else { ++liczba_wiekszych; } } // Wstawienie klucza osiowego na wlasciwe miejsce t = tab[poczatek+liczba_mniejszych]; tab[poczatek+liczba_mniejszych] = tab[poczatek]; tab[poczatek] = t; // Wywołanie rekurencyjne quicksort(tab, poczatek, liczba_mniejszych); quicksort(tab, koniec-liczba_wiekszych, liczba_wiekszych); } } // Przykladowe uzycie funkcji int main() { int tab[] = {3, 7, 5, 1, 5, 8, 4, 2}; quicksort(tab, 0, 8); return 0; }
Dodano: 5 stycznia 2018 18:56, ostatnia edycja: 13 lutego 2019 16:40.
Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.
Problem wydawania reszty (ang. change-making problem) – problem obliczeniowy polegający na tym, aby mając określony zbiór nominałów wyrazić daną kwotę za pomocą jak najmniejszej liczby monet. Jest to szczególny przypadek problemu plecakowego.
Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.
Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).
Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e(f(X)−f(X'))/T (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.