LouiS0616さんとの問答

[haruo-wakakusa]

teratailのLouiS0616さんとの問答。teratailのコメントから引用。

@anndonut さん
証明拝見しました。（安藤さんでも若草さんでも無かったのですね）
なかなかおもしろかったです。

さて、私の理解が及んでいないだけかもしれませんが、幾つか気になる点を挙げさせて頂きます。

---

1. 第3章『バブルソート』で『任意の正の整数 j, k について j ≤ k ≤ i ⇒ Sji ≤ Ski』をバブルソートの性質としていること

ステップ1の配列が {1, 2, 3, 8, 2} だったとき、ステップ2では {1, 2, 2, 3, 8} になります。
j ≤ k ≤ i を満たす j = 1, k = 2, i = 4 について、Sji ≤ Ski は成立しません。(8 ＞ 3)

---

2. 第1章『最小値を求める』で『y ∊ {A1, ... An} について xi ≤ y であるので』と記述していること

yは初出ですが、∀y ∊ {A1, ... An}, xi ≤ y という意味ですか？
これは当該アルゴリズムでxiが最小値になるという前提が無いと成立しないと思うのです。証明すべき事項を前提に持ってきて、循環してしまっているような気がします。

---

3. 第4章『バブルソートの改良アルゴリズム』で、『～であるので、ステップ i の計算完了時にステップ k = inext である』と導出していること

ステップi ⇒ 配列がある性質を満たす ことは示していますが、その逆が成立することには文中で触れていないですよね。
重箱の隅かもですが、自明とまでは言えない気がします。

---

ケチを付けるような形になって恐縮ですが、お許し願います。このように議論する機会はあまり無いですから。
単に私の理解が追い付いていない可能性も充分あり得ます。その場合はごめんなさい。

[haruo-wakakusa]

一問ずつ回答させていただきます。

1. 第3章『バブルソート』で『任意の正の整数 j, k について j ≤ k ≤ i ⇒ Sji ≤ Ski』をバブルソートの性質としていること

ステップ1の配列が {1, 2, 3, 8, 2} だったとき、ステップ2では {1, 2, 2, 3, 8} になります。
j ≤ k ≤ i を満たす j = 1, k = 2, i = 4 について、Sji ≤ Ski は成立しません。(8 ＞ 3)

「バブルソートのステップi」という表記なので混乱があるのかと思いますが、「バブルソートのステップiが満たす性質」について言及しています。例えば{1, 2, 3, 8, 2}はステップ1, 2ではありますがステップ3ではありません。ステップ3は1≤2≤3と3≤8, 3≤2を要求するが満たさないためです。{1, 2, 2, 3, 8}はステップ1, 2, 3, 4であります。ソート済みなのでステップ1からn-1までのすべてを満たします。

[haruo-wakakusa]

2. 第1章『最小値を求める』で『y ∊ {A1, ... An} について xi ≤ y であるので』と記述していること

yは初出ですが、∀y ∊ {A1, ... An}, xi ≤ y という意味ですか？
これは当該アルゴリズムでxiが最小値になるという前提が無いと成立しないと思うのです。証明すべき事項を前提に持ってきて、循環してしまっているような気がします。

最小値の算出アルゴリズムについては数学的帰納法を用いてもう少し丁寧に証明すべきかもしれませんね。検討させていただきます。

[haruo-wakakusa]

3. 第4章『バブルソートの改良アルゴリズム』で、『～であるので、ステップ i の計算完了時にステップ k = inext である』と導出していること

ステップi ⇒ 配列がある性質を満たす ことは示していますが、その逆が成立することには文中で触れていないですよね。
重箱の隅かもですが、自明とまでは言えない気がします。

ここは私の中で混乱があると思います。
『～であるので、ステップ i の計算完了時にステップ k = inext である』
は
『～であるので、ステップ i の計算完了時に配列がステップ kであることが示される。ここで、inextはk + 1となる』
というのが正しい表現かと思います。inextはインクリメントする役割の変数なので+1されていなければおかしいということなのですけれども…。ここは本文を直しておきます。

[LouiS0616]

なるほど、ステップについては完全に私の誤読でした。
『ステップn-1についてはソートが完了している』というのは、『ステップn-1 ⇔ ソートが完了』という意味だったのですね。『ステップn-1 ⇒ ソートが完了』と読んでいました。