メモリ書き込み回数を最小にするサイクルソートと呼ばれるアルゴリズムがあることを知ったとき、私はインターネットを閲覧していました.しかし、どこにもアルゴリズムを見つけることができません.サイクルが存在するかどうかを検出する方法配列?このアルゴリズムを完全に説明できる人はいますか?
2 に答える
サイクル ソート アルゴリズムは、サイクル分解と呼ばれるものによって動機付けられています。サイクル分解は、例によって最もよく説明されます。次の配列があるとします。
4 3 0 1 2
次に示すように、このシーケンスがソートされていると想像してみましょう。
0 1 2 3 4
シャッフルされたバージョンに到達するには、このソートされた配列をどのようにシャッフルする必要があるでしょうか? さて、それらを並べて配置しましょう。
0 1 2 3 4
4 3 0 1 2
最初から始めましょう。数字の 0 が最初に 2 が保持していた位置にスワップされたことに注意してください。数字の 2 が、最初に 4 が保持していた位置にスワップされました。最後に、4 が最初に 0 が保持していた位置にスワップされました。つまり、要素 0、2、および 4 はすべて、1 つ前の位置に循環されました。1 と 3 が残ります。1 は 3 に、3 は 1 に置き換えられます。言い換えると、要素 1 と 3 は 1 つ前の位置に循環されました。
上記の観察の結果として、シーケンス 4 3 0 1 2 はサイクル分解 (0 2 4)(1 3) を持っていると言えます。ここで、括弧内の用語の各グループは、「これらの要素を循環的に循環させる」ことを意味します。これは、0 を 2 のスポットに、2 を 4 のスポットに、4 を 0 のスポットに循環させ、1 を 3 のスポットに循環させ、3 を 1 のスポットに循環させることを意味します。
特定の配列のサイクル分解がある場合は、すべてを 1 箇所逆方向に循環させるだけで、書き込み回数を最小限に抑えてソートされた順序に戻すことができます。循環ソートの背後にある考え方は、入力配列の循環分解が何であるかを判断し、それを逆にしてすべてを元の場所に戻すことです。
これの課題の一部は、すべてが最初にどこに属しているかを把握することです。これは、循環分解がこれを知っていることを前提としているためです。通常、循環ソートは、各要素に移動し、それよりも小さい要素の数を数えることによって機能します。これはコストがかかります。並べ替えアルゴリズムの Θ(n 2 ) 実行時間に影響しますが、書き込みは必要ありません。
誰かが必要な場合は、ここにPythonの実装があります
def cycleSort(vector):
writes = 0
# Loop through the vector to find cycles to rotate.
for cycleStart, item in enumerate(vector):
# Find where to put the item.
pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 < item:
pos += 1
# If the item is already there, this is not a cycle.
if pos == cycleStart:
continue
# Otherwise, put the item there or right after any duplicates.
while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1
# Rotate the rest of the cycle.
while pos != cycleStart:
# Find where to put the item.
pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 < item:
pos += 1
# Put the item there or right after any duplicates.
while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1
return writes
x = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
w = cycleSort(x)
print w, x