Sortowanie – zagadnienie polegające na uporządkowaniu elementów zbioru rosnąco lub malejąco według pewnego klucza. Zagadnienie to, ze względu na częstość występowania, jest bardzo istotne dla informatyki. Istnieje wiele różnych algorytmów realizujących sortowanie.
Do oceny algorytmów sortujących można wykorzystywać takie kryteria, jak:
To, które kryteria są najważniejsze, zależy od konkretnego przypadku. Przykładowo: jeśli wiemy, że dane z dużym prawdopodobieństwem będą wstępnie posortowane, istotnym kryterium może okazać się naturalne zachowanie algorytmu. Jeśli zaś wiemy, że algorytm będzie sortował jedynie niewielkie liczby elementów, to od złożoności czasowej ważniejsza może okazać się prostota implementacji.
Algorytm | Zł. czasowa (średnia) |
Zł. czasowa (pesymistyczna) |
Stabilny | Sortowanie w miejscu |
Zachowanie naturalne |
Możliwość zrównoleglenia |
---|---|---|---|---|---|---|
Sortowanie bąbelkowe | O(n2) | O(n2) | tak | tak | nie | nie |
Sortowanie przez wstawianie | O(n2) | O(n2) | tak | tak | tak | nie |
Sortowanie przez scalanie | O(n logn) | O(n logn) | tak | nie | nie | tak |
Sortowanie szybkie (quicksort) | O(n logn) | O(n2) | nie | nie | nie | tak |
Bogosort | O(n!) | O(∞) | nie | tak | nie | ? |
Dodano: 28 stycznia 2017 18:33, ostatnia edycja: 5 stycznia 2018 19:17.
Sortowanie – zagadnienie polegające na uporządkowaniu elementów zbioru rosnąco lub malejąco według pewnego klucza. Zagadnienie to, ze względu na częstość występowania, jest bardzo istotne dla informatyki. Istnieje wiele różnych algorytmów realizujących sortowanie.
Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.
Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.