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?
ds.algorithms
total-ordering
sorting
Zachary Vance
quelle
quelle
Antworten:
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.
quelle
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.
quelle