単純挿入ソート法の要素の比較回数についての問題

質問

単純挿入ソート法の要素の比較回数、移動回数についての問題
『単純挿入ソート法は、シャトルソート法とも呼ばれ、挿入とシフトを用いるソートである。
下図（添付図）はこのソート法の１ステップを示している。
配列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
と考えているのですが自信がありません。
そもそもここで問われているオーダーとは回数のことをいってるのか、そうではないのかが分かりません。

どなたか説明していただけますと大変助かります。解答以外にもこの問題に関連することに対してのアドバイスなどがありましたら答えてくださると嬉しいです。
時間がなくて少し焦っています。どうか何卒よろしくお願いします。

回答No.5

和泉 博（@hiroshi09s）

実際に乱数を使って行ったところでは、比較＝移動回数の関係があり、処理時間と比較、移動回数は比例する関係にあって、添付図に示した Gnuplot から、O(x^2) の関係にあります。正確なカーブフィッティング値は Gnuplot によれば
f(x) = (1.92557e-9)*x^2
となりました。

/* GCC on MacOSX
----- sort.dat ファイル -----
n, sec, comp, move
-----------------------
1000 0.003 248309 248303
2000 0.011 1006037 1006029
4000 0.034 3973471 3973463
8000 0.126 15946938 15946931
16000 0.492 63930736 63930726
*/
#include <stdio.h>
#include <stdlib.h> /* srand(), rand() */
#include <time.h> /* time() */
#include <sys/time.h> /* gettimeofday() */
#define N 20000
void sort(int n, int data[]);

int main(void)
{
int i, n, data[N];
struct timeval tv;
struct timezone tz;
double before, after;

srand((unsigned)time(NULL));
for(i = 0; i < N; i++)
data[i] = rand() % N;

fprintf(stderr, "n? ");
scanf("%d", &n);

gettimeofday(&tv, &tz);
before = (double)tv.tv_sec + (double)tv.tv_usec * 1.0e-6;

sort(n, data);

gettimeofday(&tv, &tz);
after = (double)tv.tv_sec + (double)tv.tv_usec * 1.0e-6;
fprintf(stderr, "%d: %.3f sec\n", n, after - before);

return 0;
}

void sort(int n, int data[])
{
int i, j, temp;
int comp = 0, move = 0;
for (i = 1; i < n; i++) {
temp = data[i];
if (comp++, data[i-1] > temp) {
j = i;
do {
move++, data[j] = data[j-1];
j--;
} while (comp++, j > 0 && data[j-1] > temp);
move++, data[j] = temp;
}
}
printf("comp= %d move= %d\n", comp, move);
}

回答No.4

ichhabehunger

こんばんは。

nの２乗とnの１乗を比べた場合、nを大きくしていくと
圧倒的にnの２乗の方が速く大きくなります。
このとき、nの２乗から見ればnの１乗は無視できるほどの値ということになります。
こういう場合、nの２次式は「nの２乗のオーダーで大きくなる」と言うのです。
nの２次式　an^2+bn+c　はn^2から見れば bn も c も無視できる大きさとということになり、
係数 a , b , c の大きさにかかわらずオーダーは nの２乗と考えます。

回答No.3

επιστημη（@episteme）

> 要素の比較回数

挿入位置を探すのは(昇順に並んでいるんだから)二分法が使えるのでΟ(logN)じゃないかしら。

回答No.2

Tacosan

「比較回数のオーダー」とか「移動回数のオーダー」とか書いてあるんだから, 当然オーダーは「回数」のことをいっているにきまってますよ. それ以外の何だと思えるのでしょうか?

回答No.1

jjon-com

問(4)は，比較回数が n(n-1)/2 回なので，計算量（オーダ）は ｎの2乗
問(5)も，移動回数が n(n-1)/2 回なので，計算量（オーダ）は ｎの2乗

http://okwave.jp/qa/q6071509.html の私の過去の回答ANo.3
http://okwave.jp/qa/q6115906.html の私の過去の回答ANo.1
http://okwave.jp/qa/q4001070.html の私の過去の回答ANo.1