Sortowanie

Sortowanie przez wstawianie (1) Przykład algorytmu sortującego – sortowanie przez wstawianie
REKLAMA Algorytmy. Ćwiczenia
34,90 zł
Jak naprawić sprzęt elektroniczny. Poradnik dla nieelektronika. Wydanie II
−40%29,40 zł
Spring w akcji. Wydanie V
−30%62,30 zł
Opus magnum C++. Misja w nadprzestrzeń C++14/17. Tom 4
−40%29,40 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: 0 Tak Nie
Liczba głosów: 0.

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 Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną.

→ Czytaj całość
Polityka prywatnościKontakt