Wir haben eine unsortierte Folge von N Zahlen (1, 2, 3, 4, ... N). Wir können die gesamte Sequenz sortieren, indem wir benachbarte Elemente in einer bestimmten Reihenfolge vertauschen. Wie berechnet man für eine Sequenz die minimal möglichen Swaps, die zum Sortieren der Sequenz erforderlich sind?
Betrachten Sie als Beispiel die Reihenfolge {4, 2, 5, 3, 1}.
Der beste Weg, dies zu sortieren, ist die Verwendung von 7 Swaps in der folgenden Reihenfolge:
Ein gieriger Algorithmus erwies sich als nicht fruchtbar. Ein Gegenbeispiel war einfach zu konstruieren. Die nächste naheliegende Wahl für die Annäherung an die Lösung war die dynamische Programmierung.
Nehmen wir an, wir haben eine unsortierte Sequenz: {A1, A2, ... Ai, A (i + 1), ..., An}. Wir kennen die minimale Anzahl von Swaps, die benötigt werden, um die Sequenz zu sortieren. {Ai, A (i + 1), ..., An} ist Min [Ai, A (i + 1), ..., An}. Das Problem besteht darin, Min [A (i-1), Ai, ..., An] zu finden.
Nun, der erste Gedanke, der mir in den Sinn kam, war, einfach die Anzahl der Schritte hinzuzufügen, um A (i-1) an der richtigen Stelle in der bereits sortierten Reihenfolge {Ai, ..., An} zu platzieren. Das funktioniert: Das Beispiel in der Frage wurde mit der exakt gleichen Methode gelöst.
Aber ich konnte die Gültigkeit dieser Lösung nicht beweisen. Das ist bei mir oft der Fall. Wenn ich denke, dass ich das Problem gelöst habe, ist das Beste, was ich tun kann, einen "intuitiven" Beweis dafür zu bekommen. Ich bin in der High School und habe keine formelle Ausbildung in Algorithmen als solche. Ich mache es nur aus Interesse.
Gibt es eine strenge mathematische Notation, mit der dieses Problem formell umgesetzt und bewiesen werden kann? Kann diese Notation auf andere Probleme erweitert werden? Wie? Ich würde es begrüßen, wenn es in einer für einen Gymnasiasten nachvollziehbaren Form dargestellt werden könnte.
Dies ist ein klassisches Algorithmusproblem. Die Mindestanzahl bei Swaps entspricht der Anzahl der Inversionen im Array. Wenn wir den Index i und den Index j haben, so dass ein i & gt; a j und i & lt; j dann wird dies eine Inversion genannt. Lasst uns diese Aussage beweisen! Ich werde ein paar Lemmas auf dem Weg brauchen:
Lemma 1: Wenn zwei benachbarte Elemente nicht invertiert sind, wird das Array sortiert.
Beweis: Nehmen wir an, dass keine zwei benachbarten Elemente eine Inversion bilden. Dies bedeutet, dass ein i & lt; = a i + 1 für alle i in dem Intervall [0, n-1] gilt. Da <= transitiv ist, bedeutet dies, dass das Array sortiert ist.
Lemma 2: Ein einzelner Austausch zweier benachbarter Elemente reduziert die Gesamtzahl der Inversionen im Array um höchstens 1.
Beweis: wenn wir tauschen zwei benachbarte Elemente a i und a i + 1 ihre relative Position in Bezug auf alle anderen Elemente in dem Array bleibt unverändert. Das heißt für alle Elemente, die nach a i + 1 waren, sind sie immer noch nach a i + 1 und für alle Elemente vor a i , sie werden immer noch vor dem a i sein. Dies bedeutet auch, dass dann, wenn ein i oder ein i + 1 eine Inversion mit einem Element a
Lemma 3: Wir müssen mindestens NI-Swaps benachbarter Elemente durchführen, um das Array zu sortieren, wobei NI die Anzahl der Inversionen im Array ist. Beweis: In einem sortierten Array gibt es keine Inversionen. Auch nach Lemma 2 kann ein einzelner Swap die Anzahl der Inversionen um höchstens eins reduzieren. Daher müssen wir mindestens so viele Swaps durchführen wie die Anzahl der Inversionen.
Lemma 4: Wir können das Array immer nach NI-Swaps benachbarter Elemente sortieren, wobei genau wie oben in NI die Anzahl der Inversionen im Array angegeben ist.
Beweis: Wenn wir annehmen, dass in unserem Array keine Inversion zweier benachbarter Elemente vorhanden ist, wird das Array nach Lemma 1 sortiert und wir sind fertig.
Sonst gibt es mindestens ein Paar benachbarter Elemente, die eine Inversion bilden. Wir können sie austauschen und somit die Gesamtzahl der Inversionen um genau ein Mal reduzieren. Wir können diese Operation genau NI mal durchführen.
Jetzt habe ich meine Aussage vom Anfang der Antwort bewiesen.
Die einzige verbleibende Frage ist, wie die Anzahl der Inversionen in einem gegebenen Array gezählt werden soll. Sie können das tun, indem Sie eine leichte Modifikation von merge sort verwenden, bei der Sie die Inversionen in der Merge-Phase ansammeln. Sie können sich diese Antwort ansehen, um Einzelheiten zur Implementierung zu erfahren. Die Gesamtkomplexität des Algorithmus ist O(n*log(n)) .
Danke @Ivaylo Strandjev Erklärung, um die Antwort ausführlicher zu machen, hier ist Java-Implementierung:
%Vor%Tags und Links algorithm