Was ist ein guter Spezialfall-Sortieralgorithmus?

13

Ich habe einen Datensatz, bei dem es sich um eine Reihe von Objekten handelt, die in einem 2D-Raster angeordnet sind. Ich weiß, dass ich eine strikte Reihenfolge habe, die von links nach rechts in jeder Zeile und von oben nach unten in jeder Spalte zunimmt. Beispielsweise,

  • 1 2 3
  • 4 6 7
  • 5 8 9

Kann ich die naive Sortierung verbessern, um den gesamten Datensatz linear zu sortieren (gemessen in Vergleichen)?

Was ist mit nd-Datensätzen? Beliebig endliche Datensätze mit einer Teilmenge von Vergleichen bekannt?

Zachary Vance
quelle
1
Können Sie eine genauere Frage stellen? Ihr erster Absatz kann gelesen werden, um anzudeuten, dass Ihre Daten bereits sortiert sind! Was genau ist Ihr Input und welchen Output wünschen Sie?
Jacques Carette
1
Ja, die Sprache ist etwas verwirrend. Es hat einige Zeit gedauert, bis mir klar wurde, dass der Datensatz aus n zu sortierenden Zahlen besteht. Diese Zahlen sind jedoch in einem Raster von sqrt (n) x sqrt (n) angeordnet, sodass jede Zeile und jede Spalte bereits sortiert ist. Ist es das, was du meintest?
Ja das ist, was ich meinte. Ich werde aus Gründen der Übersichtlichkeit nachbearbeiten.
Zachary Vance

Antworten:

19

Es ist einfach, eine Untergrenze von Ω (n 2 log n) für dieses Problem zu beweisen (im Vergleichssortiermodell): Wenn das Element an Position (i, j) immer innerhalb des Abstands 1/2 von i + j liegt, dann das Gitter Diagonalen sind unabhängig voneinander und die Reihenfolge innerhalb jeder Rasterdiagonale ist beliebig. Unter dieser Bedingung ist also die Gesamtzahl der möglichen Ordnungen das Produkt (über alle Diagonalen des Gitters) der Fakultäten der Längen der Diagonalen, das in n 2 log n exponentiell ist .

Dies bedeutet, dass Standardsortieralgorithmen für Vergleiche für die von Ihnen beschriebenen Rasterarten asymptotisch optimal sind.

David Eppstein
quelle
Die andere Antwort gibt einen expliziten Algorithmus mit dieser Komplexität an. Daher werde ich dieses Problem für 2D-Gitter und, ohne es tatsächlich zu überprüfen, wahrscheinlich für beliebige Dimensionsgitter als gelöst betrachten.
Zachary Vance
4

Wenn ich das Problem richtig verstehe (und ich kann es auch nicht sagen), möchten Sie ein 2D-Gitter in ein sortiertes 1D-Array umwandeln, während jede Zeile und Spalte bereits im 2D-Gitter sortiert ist?

Das erste Element in der Liste muss in diesem Fall die linke obere Ecke ((0,0) laut Definition des Problems) sein. Danach muss es entweder das (1,0) oder (0,1) Element sein, da alle anderen per Definition größer sind.

Sie können verallgemeinern, indem Sie sagen, dass sich das nächstkleinere Element im Raster immer direkt unter einem bereits verwendeten Element (oder der Kante des Rasters) und auch rechts von einem bereits verwendeten Element (oder der Kante des Rasters) befindet, da beide Elemente vorhanden sind als kleiner definiert. Sie müssen also bei jeder Iteration nur den kleinsten Wert berücksichtigen, der diese Anforderung erfüllt.

Sie können die möglichen Kandidaten nacheinander sortieren (es werden nie mehr als zwei Kandidaten in einer Iteration verfügbar gemacht) und bei jeder Iteration die neuen verfügbaren Werte überprüfen (falls vorhanden). Wenn sie niedriger sind als die niedrigsten der vorherigen Kandidaten, fügen Sie sie sofort zur Liste hinzu und wiederholen Sie den Vorgang. Andernfalls fügen Sie die niedrigsten vorherigen Kandidaten hinzu und vergleichen Sie sie mit den nächstniedrigeren usw.

Leider behaupte ich nicht, in der Lage zu sein, eine genaue Komplexität zu liefern, und ich behaupte auch nicht, dass dies die effizienteste ist. Es scheint sicherlich besser zu sein als ein naiver Ansatz, und ich hoffe, ich habe es gut genug erklärt, damit Sie es verstehen.

BEARBEITEN: Für nd-Gitter wie dieses gilt meines Erachtens dasselbe Grundprinzip, aber jede Iteration stellt bis zu n neue Kandidaten zur Verfügung, und diese Kandidaten müssen zu diesem Zeitpunkt die kleinsten nicht verwendeten Elemente in jeder der n Dimensionen sein.

Paul
quelle
Kurz gesagt, können Sie eine sqrt (N) -way-Zusammenführung durchführen, wie in mergesort? Das war meine beste Methode, aber es stellt sich heraus, dass es O (N log N) ist - ich habe dort keine exakte Konstante, aber es gibt mindestens 0,5 für log (sqrt (N)).
Zachary Vance