0

サイズnのデータセットで修正されたバブルソートによって行われた比較の数を見つける必要がある宿題の割り当てに取り組んでいます。考慮されるデータセットは、最初と最後の要素が交換されるソートされたリストです。例：52341。以下は、アルゴリズムの擬似コードです。

i <- n-1; new_i <- i
while i > 0 do 
    for j=1 to i do
        if A[j] > A[j+1] do
            A[j] <=> A[j+1]
            new_i <- j
        endif
    endfor
    i <- new_i - 1; new_i <- i
endwhile

Aはデータセットで、<=>はスワップです。

与えられたタイプのデータセットでの比較の量の表現に単純化される合計でこのアルゴリズムを表す方法を見つけようとしています。

答えを出さずに、誰かが私を正しい方向に押し進めることができますか？

4

1 に答える 1

2

バブルソートの実装では、比較の数は入力のサイズだけで完全に決定されます。つまり、入力リスト内の要素の順序は重要ではありません。

この点を証明できれば（それほど難しくはありません）、サイズNの入力リストの比較の数を数えるだけで十分です。順序は重要ではないことをすでに示したので、これもかなり簡単です。

外側のwhileループと内側のforループの2つのループがあります。外側のループはnから1（またはn-1から0ですが、コードで示唆されているように、n-1から1ではありません）になります。つまり、N回の反復があります。内側のループは1からiになります。

したがって、外側のループの最初の反復でN回の比較があり、2回目でN-1、3回目でN-2、...、NN番目で0です。

一人でここまで来たと思います。そうでなければ、とにかくあなたはねじ込まれています。

あなたの先生が今見たいのは、あなたが次の公式、いわゆる「ガウス和」としても知られている「ガウス和」を知っているということです。

N +（N-1）+（N-2）+ ... +（N-N + 1）+（NN）= N ^ 2/2 + N / 2

したがって、ここで行うことになっていることは次のとおりです。

  • 比較の数が入力のサイズにのみ依存することを示します
  • 比較の数がN+（N-1）+（N-2）+ ... +（N-N + 1）+（NN）に等しいことを示します
  • ガウス氏に言及して、これはN ^ 2/2 + N/2と同じであることに言及します。

;-)

于 2012-09-21T11:18:06.847 に答える