次のような配列があるとします: [5 4 1 2 3]
そして、ソートされていない順列をソートするために必要な最小スイッチを計算したいと思います。
この場合の答えは 7 です。4 と 5 を右に移動するか、1、2、3 を左に移動します。
皮肉なことに、メモで [4 5 1 2 3] を使用すると、6 になり、自分を誤解させ、自分をばかにしてしまいます。
手順:
[5 1 4 2 3] // ステップ 1
[1 5 4 2 3] // ステップ 2
[1 5 2 4 3] // ステップ 3
[1 2 5 4 3] // ステップ 4
[1 2 5 3 4] // ステップ 5
[1 2 3 5 4] // ステップ 6
[1 2 3 4 5] // ステップ 7
私は、必要なオフセットを維持する配列を用意し、ループごとに、全体を目標に近づけるスイッチを探すなどのことを考えました。
しかし、それは遅すぎるように思えます。何かアイデアはありますか?
編集: コメントから: 配列のメンバーは、数値を繰り返さずに、サイズ N の配列に設定された {1..N} に完全に属することが保証されていますか?
いいえ。サイズが N の配列では、繰り返さない、または [1...n] に含まれないことが保証されていません。
アップデート：
この特定の問題には 2 つの解決策があります。1 つは遅いがより単純なバブルソートであり、もう 1 つは高速ですが単純ではないマージソートです。
バブルソートでは、基本的にアルゴリズムを実行するときにスイッチの数を数えます。
マージソートを使用すると、もう少しトリッキーになりますが、マージ時にカウントが行われます。配列が既にマージされている場合、この配列をソートするためのスイッチは必要ないため、カウントは 0 になるはずです。バブルソートでは、最大または最小の数字を左または右に押したときにスイッチをカウントします。マージソートを使用すると、マージ時にスイッチをカウントします。私は少し手書きのブルートフォースであなたをそこに連れて行きます。