Kiedy jest używany każdy algorytm sortowania? [Zamknięte]

Jakie są przypadki użycia, gdy konkretny algorytm sortowania jest preferowany w stosunku do innych - sortowanie przez scalanie, sortowanie przez sortowanie, sortowanie na stosach, sortowanie w trybie wstępnym itp.?

Czy istnieje zalecany przewodnik dotyczący ich używania w oparciu o rozmiar, typ struktury danych, dostępną pamięć i pamięć podręczną oraz wydajność procesora?

Najpierw definicja, ponieważ jest bardzo ważna: stabilne sortowanie to takie, które gwarantuje, że nie zmieni kolejności elementów z identycznymi kluczami.

Zalecenia:

Szybkie sortowanie: gdy nie potrzebujesz stabilnego sortowania, a średnia wydajność sprawy ma większe znaczenie niż wydajność najgorszego przypadku. Szybkie sortowanie to średnio O (N log N), w najgorszym przypadku O (N ^ 2). Dobra implementacja wykorzystuje pamięć dyskową O (log N) w postaci miejsca na stosie do rekursji.

Sortowanie przez scalanie: jeśli potrzebujesz stabilnego sortowania O (N log N), jest to jedyna opcja. Jedyne wady to to, że wykorzystuje przestrzeń pomocniczą O (N) i ma nieco większą stałą niż sortowanie szybkie. Istnieje kilka typów scalania na miejscu, ale AFAIK wszystkie są albo niestabilne, albo gorsze niż O (N log N). Nawet sortowania O (N log N) w miejscu mają o wiele większą stałą niż zwykły stary sortowanie przez scalanie, że są bardziej teoretyczną ciekawostką niż użytecznymi algorytmami.

Sortowanie na stosie: gdy nie potrzebujesz stabilnego sortowania i bardziej zależy Ci na wydajności w najgorszym przypadku niż na średniej wydajności przypadku. Gwarantujemy, że będzie to O (N log N) i wykorzystuje przestrzeń pomocniczą O (1), co oznacza, że ​​nieoczekiwanie nie zabraknie miejsca na stosie lub stercie na bardzo dużych wejściach.

Wstęp: To jest sortowanie szybkie, które przełącza się na sortowanie na stosie po określonej głębokości rekurencji, aby obejść najgorszy przypadek O (N ^ 2) sortowania szybkiego. Prawie zawsze jest lepsze niż zwykły stary szybki sort, ponieważ otrzymujesz średni przypadek szybkiego sortowania z gwarantowaną wydajnością O (N log N). Prawdopodobnie jedynym powodem używania sortowania stosu zamiast tego są systemy o bardzo ograniczonej pamięci, w których przestrzeń stosu O (log N) jest praktycznie znacząca.

Sortowanie przez wstawianie : gdy gwarantuje się, że N jest małe, w tym jako przypadek podstawowy szybkiego sortowania lub sortowania przez scalanie. Chociaż to jest O (N ^ 2), ma bardzo małą stałą i jest stabilnym rodzajem.

Sortowanie bąbelkowe, sortowanie przez wybór : Kiedy robisz coś szybko i brudno iz jakiegoś powodu nie możesz po prostu użyć algorytmu sortowania standardowej biblioteki. Jedyną zaletą, jaką mają one w porównaniu z sortowaniem przez wstawianie, jest nieco łatwiejsza implementacja.

Sortowanie bez porównania: W pewnych dość ograniczonych warunkach możliwe jest przełamanie bariery O (N log N) i sortowanie według O (N). Oto kilka przypadków, w których warto spróbować:

Sortowanie według liczenia: gdy sortujesz liczby całkowite z ograniczonym zakresem.

Sortowanie radix: gdy log (N) jest znacznie większy niż K, gdzie K to liczba cyfr podstawy.

Sortowanie zbiorcze: kiedy możesz zagwarantować, że dane wejściowe są w przybliżeniu równomiernie rozłożone.

Szybkie sortowanie jest zwykle najszybsze, ale ma dość paskudne zachowania w najgorszych przypadkach. Jeśli więc musisz zagwarantować, że żadne złe dane Ci nie dostarczą O(N^2), powinieneś tego unikać.

Sortowanie przez scalanie wykorzystuje dodatkową pamięć, ale jest szczególnie przydatne do sortowania zewnętrznego (tj. Dużych plików, które nie mieszczą się w pamięci).

Sortowanie na stosie może sortować na miejscu i nie ma najgorszego zachowania kwadratowego, ale w większości przypadków jest średnio wolniejsze niż sortowanie szybkie.

Tam, gdzie uwzględniane są tylko liczby całkowite z ograniczonego zakresu, możesz użyć pewnego rodzaju sortowania radix, aby uczynić to bardzo szybkim.

W 99% przypadków poradzisz sobie z sortowaniem w bibliotece, które zwykle opiera się na sortowaniu szybkim.

Strona Wikipedii poświęcona algorytmom sortowania ma świetną tabelę porównawczą.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

To, czego nie uwzględniają podane linki do porównań / animacji, to sytuacja, w której ilość danych przekracza dostępną pamięć - w którym momencie liczba przejść przez dane, tj. Koszty I / O, dominuje w czasie wykonywania. Jeśli musisz to zrobić, poczytaj o „sortowaniu zewnętrznym”, które zwykle obejmuje warianty sortowania przez scalanie i sterty.

http://corte.si/posts/code/visualisingsorting/index.html i http://corte.si/posts/code/timsort/index.html również zawierają fajne obrazy porównujące różne algorytmy sortowania.

@dsimcha napisał: Sortowanie zliczaniem: Kiedy sortujesz liczby całkowite z ograniczonym zakresem

Zmieniłbym to na:

Sortowanie według liczenia: podczas sortowania dodatnich liczb całkowitych (0 - Integer.MAX_VALUE-2 ze względu na szufladkę).

Zawsze możesz uzyskać wartości maksymalne i minimalne jako heurystykę wydajności również w czasie liniowym.
Potrzebujesz także co najmniej n dodatkowego miejsca na tablicę pośrednią i jest oczywiście stabilna.

/**
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

(nawet jeśli faktycznie pozwoli to na MAX_VALUE-2) zobacz: Czy tablice Java mają maksymalny rozmiar?

Chciałbym również wyjaśnić, że złożoność sortowania radix wynosi O (wn) dla n kluczy, które są liczbami całkowitymi o rozmiarze w. Czasami w jest przedstawiane jako stała, co uczyniłoby sortowanie radix lepszym (dla wystarczająco dużego n) niż najlepsze algorytmy sortowania oparte na porównaniach, które wszystkie wykonują O (n log n) porównań w celu sortowania n kluczy. Jednak generalnie w nie można uznać za stałą: jeśli wszystkie n kluczy są różne, to w musi być co najmniej log n, aby maszyna o swobodnym dostępie mogła przechowywać je w pamięci, co daje w najlepszym przypadku złożoność czasową O (n log n). (z wikipedii)