プログラミング学習の記録 633.3 11章(探索とソート)の練習問題6 『初めてのコンピュータサイエンス』(Jennifer Campbell, Paul Gries, Jason Montojo, Greg Wilson 著、長尾 高弘 訳、オライリー・ジャパン、2010年、ISBN978-4-87311-463-7)

開発環境

• Mac OS X Snow Leopard (OS)
• WingIDE
• Script言語: Python

『初めてのコンピュータサイエンス』(Jennifer Campbell, Paul Gries, Jason Montojo, Greg Wilson 著、長尾 高弘 訳、オライリー・ジャパン、2010年、ISBN978-4-87311-463-7)の11章(探索とソート), 11.7(練習問題), 6を解いてみる。

 

6.

選択ソートにソートされた長さLのリストを与えたとき、比較とコピーは、

N+(N-1)+・・・+1=N(N+1)/2 回

行われる。

挿入ソートに上記と同じリストを与えたときも比較回数は挿入ソートの場合と同じ。

逆順にソートされたリストを与えた場合も、リストに含まれるすべての値が同じ場合も同様。