c++ - 可能な限り最も単純なバブルソート

Question

サイズnの整数の配列を並べ替えたいとします。スワップ方式があるとしましょう

私のこのバブルソートの実装は正しいですか？

for(int i=0;i<n;i++)
 for (int j=0;j<n;j++)
  if (array[i]<array[j]) swap(array[i], array[j]);

（私はそれが正しいかどうかを知りたいだけです、私は非効率性を気にしません）

Answer 1

降順の並べ替えには正しくありません。

考えてarray = [2, 1]、出力[1, 2]

j=0次のように変更することで修正できますj=i+1

for(int i=0;i<n;i++)
 for (int j=i+1;j<n;j++)
  if (array[i]<array[j]) swap(array[i], array[j]);

ただし、昇順の並べ替えには適切です。

ここでの簡単な証明：

出力forループの各ステップの後に、これをsuppose_ia[0] <= a[1] <= ... <= a[i-1] <= a[i]と呼びます。

suppose_iが正しいのはi = 0

suppose_iが0<=i <M<=Nに対して正しい場合。の場合i = M、がありa[0] <= a[1] <= ... <= a[M - 2] <= a[M - 1]ます。j0からMへの内部ループの後、。を取得しa[0] <= a[1] <= ... <= a[M - 2] <= a[M - 1] <= a[M]ました。jM +1からN-1まで内部ループを続けると、a[M]はさらに大きくなります。したがって、suppose_iは。に対しても正しいですi = M。

Answer 2

はい、それは正しいです。証明は、次の線に沿って作成できます。

常にjループ（内側）が完了すると（つまり、j = n、iは次の操作として増加します）、a [i]が最大であり、a [i]の前の部分が昇順です（以下の証明） 。したがって、外側のサイクルがi = n-1で完了しようとしているとき、a [i]は最大であり、インデックスiまでのアイテムが順序付けられます（前のアイテムはいずれもmaxより大きくないため）。したがって、配列全体が注文されました。

jループが単純な後にa[i]が常に最大であることを証明するには、jループ中にiは変化せず、jがa [i]より大きいアイテムに遭遇した場合、それはa[i]になります。 jは配列全体をスキャンしましたが、a[i]より大きい要素が含まれている可能性はありません。

私までのアイテムが注文されたことを証明することは完全な誘導です。a[i]が最大であるという上記のステートメントを使用します。
i = 0の場合、些細なことです（先行する要素はありません）。a [0]は最大で、「注文済み」です。
i = 1（楽しみのために）：1つのアイテムがa [0]に到達し（その値は気にしないでください。最大値を超えることはできません）、a[1]は最大値です。したがって、a[0..1]がソートされます。

ここで、i = kで終了するjループの後でこれらが満たされると、次のようになります
。i <-k+1
現在のアイテムa[i]=qとしましょう。
jはa[]をkにスキャンします。kは最大であるため、iにスワップされます。私以外のアイテムはまだ気になりません。つまり、本質的にmaxは1つ上に移動するので、1つの項目、特にqが配列の最初の部分に追加されました。方法を見てみましょう。
インデックスmでa[i]より大きいアイテムが見つかるまで、最大までソートされたパーツがjによってスキャンされます。（最悪の場合、a [i-1]が検出されます。）mまでのアイテムがソートされます。ここにa[i]が挿入され、[m..i-1]の範囲内のすべてのアイテムが1つ上に移動します。mはa[i]を挿入するのに適切な場所であるため、移動後にa[0..i]が注文されます。ここで証明する唯一のことは、[m..i]のjループが実際に移動を実行することです。
最初にシーケンスa[i]、a [m..i-1]が順序付けられているため、この間隔でのすべての比較によってスワップがトリガーされます。a[i]は常にa[j..i]の中で最小です。部。スワップ（iとj）により、j番目が適切な場所（前面の最小アイテム）になり、jは間隔の残りの部分に進みます。
したがって、jはi = k + 1（ここではスワップなし）に到達し、a [k + 1]は最大であるため、このjループでこれ以上スワップが発生しないため、最後にa [0..k+1]がソートされます。

したがって、最後に、これらがi = kに当てはまる場合、jループの後にi = k+1に当てはまります。私たちは、1つのjループの後にi = 0を保持することを確立しました。また、i-loopから、合計n個のjループが存在することを示しているため、これらはi=n-1を保持します。これはまさに私たちが約束したことです。最初の段落で証明する。