Sortowanie

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

Algorytmy. Ilustrowany przewodnik
−30%38,43 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: 1.

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

REKLAMA

Zobacz też

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość

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ą.

→ 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