Czy nie ma algorytmu sortowania ze wszystkimi konkretnymi pożądanymi właściwościami?

22

Na stronie internetowej Sorting Algorytmy wysunięto następujące oświadczenie:

Idealny algorytm sortowania miałby następujące właściwości:

Stabilny: nie zmienia się kolejności klawiszy równych.

Działa w miejscu, wymagając dodatkowej przestrzeni. $O(1)$

Porównania klawiszy w najgorszym przypadku . $O(n\cdot\lg(n))$

Zamiany najgorszym przypadku . $O(n)$

Adaptacyjny: Przyspiesza do gdy dane są prawie posortowane lub gdy istnieje kilka unikalnych kluczy. $O(n)$

Nie ma algorytmu, który posiadałby wszystkie te właściwości, dlatego wybór algorytmu sortowania zależy od aplikacji.

Moje pytanie brzmi: czy to prawda?

nie ma algorytmu [sortowania], który posiadałby wszystkie te właściwości

a jeśli tak, to dlaczego? Co takiego jest w tych właściwościach, że uniemożliwia spełnienie wszystkich z nich jednocześnie?

algorithms sorting

— James Faulcon
źródło

4

Prawdopodobnie oznaczają po prostu, że żaden znany algorytm sortowania nie ma wszystkich tych właściwości.

— Yuval Filmus,

3

Czy istnieje choćby jedno spotkanie sortowania oparte na porównaniu 3 i 4?

— greybeard

4

@JohnFeminella Potrzebuje przynajmniej porównania , ale jak to mówi nam nic o liczbie swap?

Ω (n \cdot \log (n))

$\Omega(n \cdot \log(n))$

— Tom van der Zanden,

2

@JohnFeminella Nitpick: „lepszy niż ” jest pustą instrukcją. Powinieneś użyć lub jeśli chcesz rozmawiać o dolnych granicach.

O (_)

$O(\_)$

Ω

$\Omega$

Θ

$\Theta$

— Raphael

1

Każdy algorytm sortowania można ustabilizować, dodając jako klucz pomocniczy pierwotną pozycję elementu. Jednak to sprawia, że nie jest na miejscu, ponieważ zajęłoby O (n) dodatkową pamięć.

— Giovanni Botta,

6

WikiSort i GrailSort to dwa dość nowe algorytmy, które stosują stabilne, najgorsze porównania . Niestety nie rozumiem ich wystarczająco dobrze, aby wiedzieć, czy zbliżają się do zamiany czy też są adaptacyjne, więc nie wiem, czy naruszają czwarty i piąty warunek, jaki masz. $O(n\ lg(n))$ $O(n)$

Patrząc na artykuł „Łączenie stabilnych miejsc w oparciu o współczynnik”, autorstwa Pok-Son Kim i Arne Kutznera, do których prowadzi strona WikiSort GitHub, Kim i Kutzner twierdzą, że mają operację „scalania”, która jest (WikiSort jest odmianą Mergesort), ale nie jestem pewien, czy to przekłada się na WikiSort z zamianami . Uważa się, że GrailSort jest szybszy (na stronie GitHub WikiSort), więc mogę sobie wyobrazić, że prawdopodobnie oba mają najgorszy przypadek zamiany i są adaptacyjne. $O( m (\frac{n}{m} + 1))$ $O(n)$ $O(n)$

Jeśli komuś uda się zrozumieć WikiSort i / lub GrailSort, byłbym wdzięczny za odpowiedź na moje otwarte pytanie na ten temat

— użytkownik834
źródło

5

Dijkstry smoothsort zbliża, ale nie jest stabilna.

— vonbrand
źródło

3

Żadne znane algorytmy nie spełniają wszystkich tych właściwości. Te właściwości stały się poszukiwane, gdy opracowaliśmy więcej algorytmów sortowania. Na przykład sortowanie bąbelkowe (prawdopodobnie najbardziej prymitywny algorytm sortowania), najprawdopodobniej było niestabilne w pierwszej implementacji, ale zostało zaprojektowane tak, aby było stabilne, ponieważ informatycy starali się zwiększyć jego wydajność w późniejszych implementacjach. Informatycy najprawdopodobniej wybrali najlepsze cechy z najlepszych algorytmów, w wyniku czego powstała lista wszystkich tych pożądanych cech. W rzeczywistości trudno mieć w sobie wszystko, co najlepsze. Nie jest to niemożliwe, ale możliwe, że niemożliwe przy naszych obecnych architekturach.

PS Użyj Big-O ( ) jako asymptotycznej górnej granicy, a Big-Omega ( ) jako asymptotycznej dolnej granicy. Theta ( ) pomiędzy. $O$ $\Omega$ $\Theta$

— Siggy
źródło

1

Witamy! To miłe, ale nie rozumiem, co stabilność ma wspólnego z wydajnością: po prostu preferowane jest, aby sekcje listy z identycznymi kluczami nie były „losowo” permutowane przez algorytm.

— David Richerby,

Tak, ale jest to provably możliwe lub niemożliwe?

— James Faulcon,

1

(Chociaż jest to stare pytanie, natknąłem się na to, podobnie jak inni).

Rzeczywiście istnieje algorytm, który spełnia (1) - (4) i drugą połowę (5), więc jest bardzo zbliżony do powyższego wymogu. Jest opisany w [1] i łączy w sobie kilka sztuczek wynalezionych w ciągu ostatnich dziesięcioleci.

[1]: Franceschini, G. Theory Comput Syst (2007) 40: 327. https://doi.org/10.1007/s00224-006-1311-1

— Sebastian
źródło