- 727 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 20:41:41.34 ID:qRcqF8Uu.net]
- >>700
Aのサイズに関するinduction
♯A = 1なら自明
♯A<Nではよいとして♯A=Nとする
i = 1 で内ループが終わった状態ではA[1]に最大元が移動する
ここでi:2〜N-1でのステップでj=Nとなる時点では必ずA[i]は最大元が入ることになるので事実上A[N]は動かない
よってループはサイズがひとつ小さいサイズのArrayに対して行なっている操作と同じになる、ただしiが2〜しか走っていないが、仮に改めてもう一度i:1〜N-1で走らせてもA[1]に最大元が入っている状態からスタートなのでどのみちi=1の時点では何も起こらない事に注意する
よってi:2〜N-1まで走らせた時点で帰納法の仮定からA[1]〜A[N-1]は昇順に並んでいる
この状態で最後のi=Nのステップで全て昇順になる事は容易である□
