Gibt es keinen Sortieralgorithmus mit allen gewünschten Eigenschaften?

22

Auf der Website von Sorting Algorithms wird der folgende Anspruch geltend gemacht:

Der ideale Sortieralgorithmus hätte die folgenden Eigenschaften:

  • Stabil: Gleiche Schlüssel werden nicht neu angeordnet.
  • Funktioniert an Ort und Stelle und erfordert zusätzlichen Platz.O(1)
  • Im schlimmsten Fall Schlüsselvergleiche.O(n⋅lg⁡(n))
  • Im schlimmsten Fall Swaps.O(n)
  • Adaptiv: Geschwindigkeit bis zu wenn die Daten nahezu sortiert sind oder wenn nur wenige eindeutige Schlüssel vorhanden sind.O(n)

Es gibt keinen Algorithmus mit all diesen Eigenschaften. Die Auswahl des Sortieralgorithmus hängt daher von der Anwendung ab.

Meine Frage ist, stimmt das?

Es gibt keinen [Sortier] -Algorithmus mit all diesen Eigenschaften

und wenn ja, warum? Was ist an diesen Eigenschaften, das es unmöglich macht, sie alle gleichzeitig zu erfüllen?

algorithms sorting James Faulcon
quelle
4
Sie bedeuten wahrscheinlich nur, dass kein bekannter Sortieralgorithmus all diese Eigenschaften hat.
Yuval Filmus
3
Gibt es auch nur ein vergleichendes Sortentreffen 3 & 4?
Greybeard
4
@JohnFeminella Es braucht mindestens Vergleiche , aber wie sagt uns das etwas über die Anzahl der Swaps? Ω(n⋅Log⁡(n))
Tom van der Zanden
2
@JohnFeminella Nitpick: "besser als " ist eine leere Aussage. Sie sollten oder wenn Sie über Untergrenzen sprechen möchten. O(_)ΩΘ
Raphael
1
Jeder Sortieralgorithmus kann stabilisiert werden, indem die ursprüngliche Elementposition als Sekundärschlüssel hinzugefügt wird. Dies führt jedoch dazu, dass es nicht vorhanden ist, da es O (n) zusätzlichen Speicher benötigt.
Giovanni Botta

Antworten:

6

WikiSort und GrailSort sind zwei relativ neue Algorithmen, die stabile Schlüsselvergleiche im schlimmsten Fall durchführen . Leider verstehe ich sie nicht gut genug, um zu wissen, ob sie sich Swaps nähern oder adaptiv sind, sodass ich nicht weiß, ob sie gegen die vierte und fünfte Bedingung verstoßen, die Sie haben.O(n lG(n))O(n)

Vom Blick auf dem Papier „Ratio auf Basis stabil an Ort und Stelle Verschmelzen“ von Pok-Sohn Kim und Arne Kutzner auf der Seite WikiSort GitHub verbunden, Kim und Kutzner Anspruch einen ‚merge‘ Betrieb zu haben , das ist (WikiSort ist eine Variante von Mergesort), aber ich bin mir nicht sicher, ob das zu WikiSort mit Swaps führt. GrailSort ist angeblich schneller (auf der WikiSort GitHub-Seite), daher könnte ich mir vorstellen, dass es wahrscheinlich ist, dass beide Swaps im schlimmsten Fall haben und adaptiv sind.O(m(nm+1))O(n)O(n)

Wenn jemand es schafft, WikiSort und / oder GrailSort zu verstehen, würde ich es begrüßen, wenn er auch meine offene Frage dazu beantwortet

user834
quelle
5

Dijkstra's Smoothsort kommt nahe, ist aber nicht stabil.

vonbrand
quelle
3

Keine bekannten Algorithmen erfüllen alle diese Eigenschaften. Diese Eigenschaften wurden nachgefragt, als wir mehr Sortieralgorithmen entwickelten. Beispielsweise war die Blasensortierung (wahrscheinlich der primitivste Sortieralgorithmus) in der ersten Implementierung höchstwahrscheinlich nicht stabil, wurde jedoch als stabil konzipiert, da Informatiker versuchten, sie in späteren Implementierungen effizienter zu gestalten. Daher haben Informatiker höchstwahrscheinlich die besten Merkmale aus den besten Algorithmen ausgewählt, und als Ergebnis haben Sie eine Liste aller dieser wünschenswerten Merkmale angezeigt. In Wirklichkeit ist es schwierig, das Beste von allen Welten in irgendetwas zu haben. Nicht unmöglich, aber möglicherweise unmöglich mit unseren aktuellen Architekturen.

OΩΘ

Siggy
quelle
1
Herzlich willkommen! Das ist schön, aber ich verstehe nicht, was Stabilität mit Effizienz zu tun hat: Es ist nur eine Vorliebe, dass Abschnitte der Liste mit identischen Schlüsseln vom Algorithmus nicht "zufällig" permutiert werden.
David Richerby
Ja, aber ist das nachweislich möglich oder unmöglich?
James Faulcon
1

(Auch wenn dies eine alte Frage ist, bin ich darauf gestoßen und vielleicht auch auf andere.)

Es gibt in der Tat einen Algorithmus, der (1) - (4) und die zweite Hälfte von (5) erfüllt und somit der obigen Anforderung sehr nahe kommt. Es ist in [1] beschrieben und kombiniert mehrere Tricks, die in den letzten Jahrzehnten erfunden wurden.

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

Sebastian
quelle