Sortowanie
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.
Kryteria oceny
Do oceny algorytmów sortujących można wykorzystywać takie kryteria, jak:
- Złożoność czasowa.
- Złożoność pamięciowa. Jeśli algorytm nie potrzebuje dodatkowej pamięci (oprócz tej, w której znajdują się dane do posortowania) lub dodatkowa pamięć nie zależy od liczby elementów, algorytm ten nazywamy sortowaniem w miejscu.
- Stabilność, czyli zachowanie początkowej kolejności elementów w przypadku kluczy o tej samej wartości.
- Tzw. zachowanie naturalne. Jeśli dla danych wstępnie posortowanych (choćby częściowo) algorytm wykonuje się szybciej, niż dla zupełnie wymieszanych, to wówczas mówimy, że algorytm wykazuje zachowanie naturalne.
- Prostota implementacji.
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.
Wybrane algorytmy sortujące
| 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 | ? |
Liczba głosów: 0.
Dodano: 28 stycznia 2017 18:33, ostatnia edycja: 5 stycznia 2018 19:17.
Zobacz też
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.
Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.
Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.