単純挿入ソート法の要素の比較回数についての問題
単純挿入ソート法の要素の比較回数、移動回数についての問題
『単純挿入ソート法は、シャトルソート法とも呼ばれ、挿入とシフトを用いるソートである。
下図（添付図）はこのソート法の１ステップを示している。
配列a[0],…,a[n-1]があって、a[i]より前の部分がソートされている。
ここで、a[i]の値をwとする。 a[0],…,a[i-1]の 部分で、w が入るべき位置を探す。
この位置をj とする。配列の範囲 a[j],…,a[j-1]をa[j+1],…,a[i] ヘシフト する。最後に、wをa[j]に格納する。
このような操作を、最後まで繰り返す。
以下の問に答えよ。
問(1)～(3) 省略
問(4)単純挿入ソート法で要素の比較回数のオーダーを答えなさい。ただし、配列の要素数を n とする。
問(5)単純挿入ソート法で要素の移動回数のオーダーを答えなさい。ただし、 配列の要素数を n とする。』
問(1)～(3)は単純挿入ソート法で配列を昇順にソートするC言語で記述されたプログラムに関する問題なのですがそちらは解けました。
問(4)は比較回数のオーダーを S とすると、最悪の場合 n(n-1)/2 回 比較を行う必要があるので、S=n(n-1)/2
問(5)は移動回数のオーダーを T とすると、最悪の場合 n(n-1)/2 回 移動を行う必要があるので、T=n(n-1)/2
と考えているのですが自信がありません。
そもそもここで問われているオーダーとは回数のことをいってるのか、そうではないのかが分かりません。
どなたか説明していただけますと大変助かります。解答以外にもこの問題に関連することに対してのアドバイスなどがありましたら答えてくださると嬉しいです。
時間がなくて少し焦っています。どうか何卒よろしくお願いします。
![その他([技術者向] コンピューター) イメージ](https://gazo.okwave.jp/okwave/spn/images/related_qa/c205_3_thumbnail_img_sm.png)
補足
m-ブロック法だと、各ブロックと一回ずつ比較してｘを含んでいるブロックを決めて、 そのブロックについて逐次探索をするから、 最悪の場合はブロックを決めるのにｍ-１回比較して、 ブロック内ではブロック長ｋ＝n/m（繰り上がり）に等しい回数の比較を行う場合である。 比較回数に関して、 比較回数≦ｍ－１＋ｎ／ｍ（繰り上がり） が成り立ち、ｎ／ｍ（繰り上がり）≦ｎ／ｍ＋１より、 比較回数≦ｍ＋ｎ／ｍ が成り立つ。 相加平均と相乗平均の関係から上式の右辺が最小になるのは ｍ＝ｎ／ｍが成り立つとき、つまりｍ＝√ｎの時で、これを代入すると 比較回数は約２√ｎになるから、オーダ表現はO(√n)になる。 って感じです。 本当はこれで当たってるかも不安なんですけどね。