c++ - 帰納法を使ってバブルソートが正しいことを証明する

Question

帰納法を使用して、バブルソートが正しいことをどのように示すことができますか? 証明の定式化を通じて従うべき不変条件をどのように選択すればよいでしょうか (このステップは私には恣意的な作業のように思えるので、より深く説明できれば非常にありがたいです)。

各反復の後、最大の要素が常にリストの最後になることは理解していますが、この事実を使用してアルゴリズムが正しいことを示す方法がわかりません。

助けてくれてありがとう！

Answer 1

これがあなたが望むものかどうかはわかりませんが、彼は私がそれをどのように見ているかです.

バブル ソートの背後にある考え方は、値のベクトル (左から右) をたどるというものです。私はこれをパスと呼んでいます。パス中に値のペアがチェックされ、正しい順序になるようにスワップされます (右上)。

最初のパスで最大値に達します。最大値に達すると、その横の値よりも高くなるため、それらが交換されます。これは、max がパスの次のペアの一部になることを意味します。これは、パスが完了し、max がベクトルの右端に残されるまで繰り返されます。

2 番目のパスでは、ベクトルの 2 番目に高い値についても同じことが当てはまります。唯一の違いは、最後に最大値と交換されないことです。これで、最も右の 2 つの値が正しく設定されました。

次のパスごとに、1 つの値が右側に並べ替えられます。

N 個の値と N 個のパスがあります。これは、N が渡された後、すべての N 値がソートされることを意味します。