Sortowanie

Sortowanie przez wstawianie (1) Przykład algorytmu sortującego – sortowanie przez wstawianie
REKLAMA

Czysty kod. Podręcznik dobrego programisty
−40%41,40 zł
Algorytmy, struktury danych i techniki programowania. Wydanie V
49,00 zł

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 ?
Ocena: +1 Tak Nie
Liczba głosów: 3.

Dodano: 28 stycznia 2017 18:33, ostatnia edycja: 5 stycznia 2018 19:17.

REKLAMA

Zobacz też

Kolejka (ang. Queue) – struktura danych, w której elementy pobierane są z początku, a dodawane na końcu. Z kolejki można zatem pobrać tylko ten element, który był dodany najwcześniej. Kolejka bywa określana również jako kolejka FIFO (z ang. First In, First Out), w odróżnieniu od kolejki LIFO, czyli stosu.

→ Czytaj całość

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość

Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.

Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.

→ Czytaj całość
Polityka prywatnościKontakt