zuvor habe ich an der Sortierung einer ganzzahligen Sequenz ohne identische Zahlen gearbeitet (ohne Verlust der Allgemeinheit, angenommen, die Sequenz ist eine Permutation von 1,2,...,n ) in ihre natürliche aufsteigende Reihenfolge (d. h. 1,2,...,n ). Ich denke darüber nach, wie man die Elemente (unabhängig von den Positionen der Elemente, dh ein Swap ist für zwei beliebige Elemente gültig) mit einer minimalen Anzahl von Swaps tauschen kann. Ich denke, das Folgende ist ein praktikabler Algorithmus:
Tausche zwei Elemente mit der Einschränkung, dass eine oder beide von ihnen in die richtige Position getauscht werden sollen. Bis jedes Element in der richtigen Position ist.
Aber ich weiß nicht, wie ich mathematisch beweisen kann, ob der obige Algorithmus zur optimalen Lösung führen kann. Jeder kann helfen?
Vielen Dank.
Ich konnte dies mit der Graphentheorie beweisen. Vielleicht möchte ich dieses Tag hinzufügen in:)
Erstellen Sie ein Diagramm mit n Vertices. Erstellen Sie eine Kante vom Knoten n_i bis n_j , wenn das Element in der Position i in der richtigen Reihenfolge in der Position j stehen sollte. Sie haben jetzt ein Diagramm, das aus mehreren sich nicht überschneidenden Zyklen besteht. Ich behaupte, dass die Mindestanzahl von Swaps, die benötigt werden, um das Diagramm korrekt zu ordnen,
Nimm dir eine Sekunde, um dich davon zu überzeugen ... wenn zwei Gegenstände in einem Zyklus sind, kann ein Tausch nur für sie sorgen. Wenn sich drei Elemente in einem Zyklus befinden, können Sie ein Paar austauschen, um eines an die richtige Stelle zu setzen, und ein Zweizyklus bleibt usw. Wenn n Elemente in einem Zyklus sind, benötigen Sie n-1 swaps. (Dies gilt immer, auch wenn Sie nicht mit unmittelbaren Nachbarn tauschen.)
Vorausgesetzt, dass Sie jetzt sehen können, warum Ihr Algorithmus optimal ist. Wenn Sie einen Swap durchführen und mindestens ein Element an der richtigen Position ist, wird der Wert von M immer um 1 reduziert. Für jeden Zyklus der Länge n sollten Sie ein Element an die richtige Position, belegt mit, versetzen sein Nachbar. Sie haben jetzt ein korrekt geordnetes Element und einen Zyklus der Länge n-1 .
Da M die minimale Anzahl von Swaps ist und Ihr Algorithmus M für jeden Swap immer um 1 reduziert, muss er optimal sein.
Schön gemacht Lösung von @bekce. Bei Verwendung von C # kann der Anfangscode zum Einrichten des modifizierten Arrays ar kurz und bündig wie folgt ausgedrückt werden:
Verwenden Sie dann origIndexes anstelle von ar im Rest des Codes.
Dies ist der Beispielcode in C ++, der die minimale Anzahl von Swaps zum Sortieren einer Permutation der Sequenz von (1,2,3,4,5,.......n-2,n-1,n)
Tags und Links algorithm graph-theory sorting sequence