Sortowanie

Sortowanie przez wstawianie (1) Przykład algorytmu sortującego – sortowanie przez wstawianie
REKLAMA Thinking in Java. Edycja polska. Wydanie IV
149,00 zł
Czysta architektura. Struktura i design oprogramowania. Przewodnik dla profesjonalistów
67,00 zł
Deep Learning. Praca z językiem Python i biblioteką Keras
−30%41,30 zł
Wzorce projektowe. Elementy oprogramowania obiektowego wielokrotnego użytku
59,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: 0 Tak Nie
Liczba głosów: 0.

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

REKLAMA

Zobacz też

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość

Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.

Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.

  • Metoda zstępująca z zapamiętywaniem polega na rekurencyjnym wywoływaniu funkcji z zapamiętywaniem wyników. Metoda ta jest podobna do metody dziel i zwyciężaj – różni się od niej tym, że jeśli rozwiązanie danego problemu jest już w tabeli z wynikami, to należy je po prostu stamtąd odczytać.
  • Metoda wstępująca polega na rozwiązywaniu wszystkich możliwych podproblemów, zaczynając od tych o najmniejszym rozmiarze. Wówczas w momencie rozwiązywania podproblemu na pewno są już dostępne rozwiązania jego podproblemów. W tym podejściu nie zużywa się pamięci na rekurencyjne wywołania funkcji. Może się jednak okazać, że część podproblemów została rozwiązana nadmiarowo (nie były one potrzebne do rozwiązania głównego problemu).
→ Czytaj całość

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

→ Czytaj całość
Polityka prywatnościKontakt