Zrozum struktury danych. Algorytmy i praca na danych w Javie
−30%27,93 zł
Algorytmy. Ilustrowany przewodnik
54,90 zł
Kwalifikacja EE.08. Montaż i eksploatacja systemów komputerowych, urządzeń peryferyjnych i sieci. Część 1. Urządzenia techniki komputerowej. Podręcznik do nauki zawodu technik informatyk
37,95 zł
Czysta architektura. Struktura i design oprogramowania. Przewodnik dla profesjonalistów
67,00 zł
Kwalifikacja EE.09. Programowanie, tworzenie i administrowanie stronami internetowymi i bazami danych. Część 1. Tworzenie stron internetowych. Podręcznik do nauki zawodu technik informatyk
47,00 zł

Sortowanie

Sortowanie przez wstawianie Przykład algorytmu sortującego – sortowanie przez wstawianie

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.

Zobacz też

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

→ Czytaj całość

Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).

Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:

  • Jak rozwiązać przypadek bazowy (trywialny).
  • Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.

Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.

→ Czytaj całość

Ten artykuł opisuje pewną modyfikację algorytmu opartego na programowaniu dynamicznym rozwiązującego problem wydawania reszty. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego. Algorytm zaproponował J.W. Wright w pracy The Change-Making Problem (link w bibliografii).

→ Czytaj całość
Polityka prywatnościKontakt