Jaki jest najszybszy algorytm sortowania dla tablicy liczb całkowitych?

55

Podczas nauki w szkole średniej natknąłem się na wiele algorytmów sortowania. Jednak nigdy nie wiem, która jest najszybsza (dla losowej liczby całkowitej). Więc moje pytania to:

Który jest najszybszym obecnie znanym algorytmem sortowania?
Teoretycznie jest możliwe, że są jeszcze szybsze? Jaka jest najmniej złożoność sortowania?

— gen
źródło

6

Co rozumiesz przez „szybki”? Co chcesz mierzyć?

— Raphael

2

Co oznacza „losowa tablica liczb całkowitych”? Losowo z jaką dystrybucją? jednolita dystrybucja? Gaussa? W zależności od rozkładu algorytmy czasu działania mogą być lepsze niż

.

O (n \log n)

$\mathcal{O}(n\log{n})$

— Bakuriu

@gen Spójrz na sortowanie Radix. Prawidłowa implementacja ma na przykład złożoność O (n) dla Int32.

— to

Spójrz na test porównawczy sortowania

— adrianN

1

@gen: Pod względem

asymptotyków? To proste: wybierz dowolny z algorytmów

. Pamiętaj, że może to nie mieć nic wspólnego z (przeciętną) wydajnością w świecie rzeczywistym. Może to być warte przeczytania w tym względzie.

Θ

$\Theta$

Θ (n \log n)

$\Theta(n \log n)$

— Raphael

42

Ogólnie rzecz biorąc, istnieją algorytmy sortowania , takie jak sortowanie wstawiane, sortowanie bąbelkowe i sortowanie selekcyjne, których zwykle powinieneś używać tylko w szczególnych okolicznościach; Quicksort, który jest najgorszym przypadkiem ale dość często z dobrymi stałymi i właściwościami i który może być stosowany jako procedura sortowania ogólnego przeznaczenia; algorytmów, takich jak seryjnej-sortowania i sterty rodzaju, które są również dobre algorytmy ogólnego zastosowania do sortowania; i $O(n^2)$ $O(n^2)$ $O(n\log n)$ $O(n\log n)$ lub liniowe algorytmy sortowania dla list liczb całkowitych, takich jak podstawa, wiaderko i zliczanie, które mogą być odpowiednie w zależności od charakteru liczb całkowitych na twoich listach. $O(n)$

Jeśli elementy na liście są takie, że wszystko, co o nich wiesz, to łączna relacja między nimi, wówczas optymalne algorytmy sortowania będą miały złożoność . Jest to dość fajny wynik, dla którego powinieneś być w stanie łatwo znaleźć szczegóły w Internecie. Algorytmy liniowego sortowania wykorzystują dalsze informacje o strukturze elementów do sortowania, a nie tylko całkowitą relację kolejności między elementami. $\Omega(n\log n)$

Mówiąc bardziej ogólnie, optymalność algorytmu sortowania zależy ściśle od założeń, jakie możesz poczynić na temat rodzaju list, które zamierzasz sortować (a także od modelu maszyny, na którym algorytm będzie działał, co może sprawić, że sortowanie w jeszcze inny sposób będzie złe algorytmy najlepszym wyborem; rozważ sortowanie bąbelkowe na maszynach z taśmą do przechowywania). Im silniejsze są twoje założenia, tym więcej algorytmów można wyciąć. Przy bardzo słabych założeniach dotyczących tego, jak skutecznie można określić „sortowanie” listy, optymalna złożoność najgorszego przypadku może nawet wynosić . $\Omega(n!)$

Ta odpowiedź dotyczy tylko zawiłości. Rzeczywiste czasy działania implementacji algorytmów będą zależeć od dużej liczby czynników, które trudno jest uwzględnić w jednej odpowiedzi.

— Patrick87
źródło

O

$O$

Ω

$\Omega$

1

Θ

$\Theta$

Ω

$\Omega$

7

Ω

$\Omega$

2

@RealzSlaw: Nosiłbym to z dumą. :]

— Raphael

1

@gen Zobacz stackoverflow.com/a/3274203, aby uzyskać dyskusję. Zasadniczo, jeśli pojedyncze rekordy są ogromne i nie są przechowywane w sposób o swobodnym dostępie, a ilość danych jest taka, że należy to zrobić w miejscu, to najlepszym rozwiązaniem jest sortowanie bąbelkowe. Te okoliczności są obecnie obecnie rzadkie, ale możesz je spotkać.

— Patrick87

16

Odpowiedź, jak to często bywa w przypadku takich pytań, brzmi „to zależy”. Zależy to od (a) tego, jak duże są liczby całkowite, (b) czy tablica wejściowa zawiera liczby całkowite w losowej kolejności lub w prawie posortowanej kolejności, (c) czy potrzebujesz algorytmu sortowania, aby był stabilny, czy nie, a także inne czynniki, (d) czy cała lista liczb mieści się w pamięci (sortowanie w pamięci vs. sortowanie zewnętrzne), oraz (e) maszyna, na której ją uruchomisz.

W praktyce algorytm sortowania w standardowej bibliotece twojego języka będzie prawdopodobnie całkiem dobry (całkiem zbliżony do optymalnego), jeśli potrzebujesz sortowania w pamięci. Dlatego w praktyce wystarczy użyć dowolnej funkcji sortowania zapewnianej przez standardową bibliotekę i mierzyć czas działania. Tylko jeśli okaże się, że (i) sortowanie stanowi dużą część całkowitego czasu działania, oraz (ii) czas działania jest niedopuszczalny, powinieneś zawracać sobie głowę algorytmem sortowania. Jeśli te dwa warunki się utrzymują, możesz spojrzeć na określone aspekty konkretnej domeny i eksperymentować z innymi algorytmami szybkiego sortowania.

Ale realistycznie, w praktyce algorytm sortowania rzadko stanowi poważne wąskie gardło wydajności.

— DW
źródło

9

Ponadto, odpowiadając na twoje drugie pytanie

Teoretycznie jest możliwe, że są jeszcze szybsze?
Jaka jest najmniej złożoność sortowania?

W przypadku sortowania ogólnego zastosowania złożoność problemu sortowania na podstawie porównania wynosi Ω (n log n) . Istnieje kilka algorytmów, które wykonują sortowanie w O (n), ale wszystkie opierają się na przyjmowaniu założeń dotyczących danych wejściowych i nie są algorytmami sortowania ogólnego przeznaczenia.

Zasadniczo złożoność wynika z minimalnej liczby porównań potrzebnych do sortowania tablicy (log n reprezentuje maksymalną wysokość binarnego drzewa decyzyjnego zbudowanego podczas porównywania każdego elementu tablicy).

Formalny dowód złożoności sortowania można znaleźć tutaj :

— rla4
źródło

3

Ω (n \log n)

$\Omega(n \log n)$

Zależy od tego, co rozumiesz przez problem sortowania . Sortowania ogólnego przeznaczenia oparte na porównaniu nie są jedynym rodzajem problemów z sortowaniem, jakie mają ludzie.

— Patrick87

1

To prawda, oczywiście. Powinienem był być bardziej szczegółowy, dziękuję za zwrócenie na to uwagi. Byłem jednak trochę ciekawy, do jakich innych podejść do sortowania (nie opartych na porównaniu), o których mówisz; Sortowanie Radix jest dokładnie takim rodzajem algorytmu O (n), o którym mówiłem - musisz „założyć” coś o danych wejściowych (liczby całkowite o stałej szerokości). W tym sensie nie jest to algorytm sortowania ogólnego zastosowania, prawda?

— rla4

1

@DW: Sortowanie Radix nie powinno być uważane za algorytm sortujący „ogólnego zastosowania”, ponieważ wymaga kluczy o stałej długości; czy nie jest to użyteczne inaczej. Ale rozumiem o co ci chodzi. :) Wydaje mi się, że mój błąd polegał na sortowaniu czegoś, co można porównać, a nie na sortowaniu liczb całkowitych . Są to różne problemy i mają inny zestaw możliwych rozwiązań. Pytanie zawiera wzmiankę o „losowej tablicy liczb całkowitych”, ale przyznaję, że wziąłem ją za przykład, a nie ograniczenie.

— rla4

2

@DavidRicherby, patrząc na to po półtora roku, zgadzam się z tobą. Dziękuję Ci.

— DW

3

$O(n\log\log n)$ $O(n\log n)$

— użytkownik39994
źródło

2

n \log n

$n\log n$

Ω (n \log n)

$\Omega(n\log n)$

O (n \log \log n)

$O(n\log\log n)$

— David Richerby,

1

Przeczytałem pozostałe dwie odpowiedzi w momencie pisania tego i nie sądziłem, że żadna z nich odpowiednio odpowiedziała na twoje pytanie. Inne odpowiedzi dotyczyły obcych pomysłów na temat losowych rozkładów i złożoności przestrzeni, które prawdopodobnie nie wchodzą w zakres badań w szkole średniej. Oto moje zdanie.

$A$ $n$ $(n-1)$ $A$ $(n-1)$ $\Omega(n)$ $O(n)$ $\Omega(n)$

$\Omega(n)$ $O(n)$ $n$ $2n$ $3n-5$ $1$ $n^2$

— bourbaki4481472
źródło

O (n)

$O(n)$

n

$n$

\lg n

$\lg n$

n \leq 2^{32}

$n \le 2^{32}$

O (n)

$O(n)$

O (n \lg n)

$O(n \lg n)$ (dla szybkiego sortowania lub łączenia), w praktyce porównanie nie jest tak jasne: stałe ukryte w notacji big-O stają się bardzo ważne, a stała dla sortowania radix jest wyższa niż stała dla szybkiego sortowania lub łączenia.

— DW

l g (n)

$lg(n)$

n

$n$

Ω (n)

$\Omega(n)$

2

O (w n)

$O(wn)$

w

$w$

w

$w$

w

$w$

{0, \dots, 2^{w} - 1}

$\{0, \dots, 2^w-1\}$

\log n

$\log n$

n

$n$

w = \log n

$w=\log n$

n \log n

$n\log n$ .

— David Richerby,

1

O (n \sqrt{l o g l o g n})

$O(n \sqrt{log{ log{n}}})$

O (n \sqrt{l o g l o g U})

$O(n \sqrt{log{ log{U}}})$

U

$U$

— głupiec
źródło

0

$\log(n!)$

$\Omega(n)$

— Yves Daoust
źródło

0

Ponieważ nie wspominasz o żadnych ograniczeniach sprzętowych i ponieważ szukasz „najszybszego”, powiedziałbym, że powinieneś wybrać jeden z algorytmów sortowania równoległego w oparciu o dostępny sprzęt i rodzaj posiadanego wejścia.

W teorii np . quick_sortJest O(n log n). W przypadku pprocesorów idealnie powinno to sprowadzić się do tego, O(n/p log n)jeśli uruchomimy go równolegle.

Cytując Wikipedię: Złożoność czasowa ...

Optymalne sortowanie równoległe to O (log n)

W praktyce w przypadku ogromnych rozmiarów danych wejściowych nie byłoby możliwe O(log n)ze względu na problemy ze skalowalnością.

Oto pseudo kod dla sortowania korespondencji seryjnej . Implementacja merge()może być taka sama jak w normalnym sortowaniu scalającym:

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid = ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Zobacz także:

Który algorytm sortowania równoległego ma najlepszą średnią wydajność przypadków?
https://en.wikipedia.org/wiki/Sorting_alameterm - są linki do równoległych wersji wielu algorytmów sortujących.

— Kashyap
źródło

O (n^{2})

$\mathcal O(n^2)$

@ Evil Tak. Quicksort nie nadaje się do przetwarzania równoległego. To jest przykład. Te, które powinny być użyte, są wymienione w podanych linkach.

— Kashyap,