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(nlg(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?

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? Ω(nlog(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(_)ΩΘ
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,

Odpowiedzi:

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 )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(n)O(n)O(m(nm+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ΩΘ

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