1

私は Comb Sort についていくつかの調査を行っており、アルゴリズムが正しいことが証明されているかどうかを把握しようとしています。ただし、アルゴリズムに関する多くのドキュメントを見つけることができないようです。これは非常に単純なアルゴリズムですが、基本的にはバブル ソートの変形であり、証明は複雑ではないと思います。これに関する詳細情報をどこで見つけることができるか、またはそれを最初から証明する方法について考えている人はいますか?

Comb Sort に慣れていない方のために、ウィキペディアの記事で疑似コードを見つけることができます。

4

1 に答える 1

0

ウィキペディアの疑似コードを使用しましょう:

function combsort(array input) is
    gap := input.size
    shrink := 1.3
    sorted := false

    loop while sorted = false
        gap := floor(gap / shrink)
        if gap ≤ 1 then
            gap := 1
            sorted := true
        end if

        i := 0
        loop while i + gap < input.size
            if input[i] > input[i+gap] then
                swap(input[i], input[i+gap])
                sorted := false
            end if

            i := i + 1
         end loop
     end loop
end function

メイン ループはwhile sorted = falseであり、ループを早期に停止するステートメントはありませんbreak。これは証明に非常に役立ちます。このループが終了した場合、sorted = true. つまり、1 つ目はループが終了すること、2 つsorted = true目はループの最後で配列が実際にソートされることです。

  • 各時間sortedがfalse反復の終わりにあるため、ループは終了します。時間gapが小さくなるかgap、同じままで、配列内の反転の数が少なくなります。と反転の数はgapそれぞれ 1 と 0 で囲まれた整数であるため、無限に小さくなることはありません。
    • gap2 以上の場合、その反復で小さくなります (floor関数に注意してください)。
    • 1 の場合gapは 1 のままで、内側のループの前sortedに設定されました。スワップすることによってのみ元に戻すことができます。このようなスワップは、配列内の反転の数を 1 減らします。内側のループは、他の状況ではスワップを実行しないため、.truesortedfalseinput[i]input[i+1]iinput[i] > input[i+1]gap = 1
  • ループの最後にある場合、それ以外の場合は に設定できないため、それがsorted = trueわかります。これが一部の に当てはまらない場合は、 に設定されているため、すべてのこともわかります。したがって、配列内の隣接する要素のすべてのペアが正しい場合、つまり配列がソートされている場合にのみ、ループの最後で真になります。gap = 1sortedtrueinput[i] <= input[i+1]isortedfalsesorted
于 2020-01-23T01:39:34.590 に答える