単純挿入ソート法の要素の比較回数についての問題
単純挿入ソート法の要素の比較回数、移動回数についての問題
『単純挿入ソート法は、シャトルソート法とも呼ばれ、挿入とシフトを用いるソートである。
下図(添付図)はこのソート法の1ステップを示している。
配列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
と考えているのですが自信がありません。
そもそもここで問われているオーダーとは回数のことをいってるのか、そうではないのかが分かりません。
どなたか説明していただけますと大変助かります。解答以外にもこの問題に関連することに対してのアドバイスなどがありましたら答えてくださると嬉しいです。
時間がなくて少し焦っています。どうか何卒よろしくお願いします。