- 736 名前：708 mailto:sage [2022/10/26(水) 14:06:51.89 ID:8peJPiGV.net]
- > j=I−1 直後は A[I-1] ≦ A[I] とは限らないが
↑
少し訂正
I = 0 の場合:
明らかに内側 j ループ終了時点で A[I] に最大値が入る.
I > 0 の場合:
内側 j ループ ”処理開始”時点で A[I-1] に最大値が入っている(※帰納法の仮定に加える)ので
j=I-1 で swap が起きたら A[I-1] < A[I] , 起きなければ A[I-1] = A[I] のまま変わらない.
いずれにしろ j=I-1 ”処理終了”時点で A[I-1] ≦ A[I] が確定して A[I] に最大値が入る.
j=I 以降で swap は生じない.
