7

メモリ書き込み回数を最小にするサイクルソートと呼ばれるアルゴリズムがあることを知ったとき、私はインターネットを閲覧していました.しかし、どこにもアルゴリズムを見つけることができません.サイクルが存在するかどうかを検出する方法配列？このアルゴリズムを完全に説明できる人はいますか?

4

2 に答える 2

19

サイクル ソート アルゴリズムは、サイクル分解と呼ばれるものによって動機付けられています。サイクル分解は、例によって最もよく説明されます。次の配列があるとします。

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 ) 実行時間に影響しますが、書き込みは必要ありません。

于 2015-08-21T19:07:38.427 に答える
0

誰かが必要な場合は、ここに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
于 2016-04-09T18:52:19.597 に答える