javaのシェルソートについて質問です

質問

//Sample482
import java.util.Random;

class Sample482{
static int shellSort1(int[] x){
int n = x.length;
int cnt = 0;

for(int h = n/2;h > 0;h /= 2){
for(int i = h;i < n;i++){
int tmp = x[i];
int j;
for(j = i;j > h-1 && x[j-h] > tmp;j -= h){
cnt++;
x[j] = x[j-h];
}
x[j] = tmp;
}
}
return cnt;
}
public static void main(String[] args){
Random rand = new Random();

int n = 20000;
int[] x = new int[n];

for(int i = 0;i < n;i++){
x[i] = rand.nextInt(1000000);
}

int cnt = shellSort1(x);

System.out.println("昇順にソートしました。");

for(int i = 0;i < n;i++){
System.out.println("x[" + i + "]=" + x[i]);
}

System.out.println("要素の移動回数" + cnt);
}
}

//Sample483
import java.util.Random;

class Sample483{
static int shellSort2(int[] x){
int n = x.length;
int cnt = 0;

int h;
for(h = 1;h < n/9;h = 3*h+1);

for(;h > 0;h /= 3){
for(int i = h;i < n;i++){
int j;
int tmp = x[i];
for(j = i-h;j >= 0 && x[j] > tmp;j -= h){
x[j+h] = x[j];
cnt++;
}
x[j+h] = tmp;
}
}
return cnt;
}
public static void main(String[] args){
Random rand = new Random();

int n = 20000;
int[] x = new int[n];

for(int i = 0;i < n;i++){
x[i] = rand.nextInt(1000000);
}

int cnt = shellSort2(x);

System.out.println("昇順にソートしました。");

for(int i = 0;i < n;i++){
System.out.println("x[" + i + "]=" + x[i]);
}

System.out.println("要素の移動回数:" + cnt);
}
}

上記のSample482とSample483はどちらもシェルソートを扱ったコードです。

参考書やネットの情報によると、後者のSmple483のシェルソートの方がより高速にソート
することができるらしいのですが、実際に実行してみると、要素の移動回数は
Sample482よりSample483の方が多くなります。

要素の移動回数が多いということは、それだけソートに時間がかかると私は思うのですが、
何故、後者のシェルソートの方が高速に動くといえるのでしょうか?

回答No.1

maiko0318

移動回数は元データの並びによって変わります。
移動にはそんなに時間が変わる要素ではありません。

問題はループ回数です。
１００個の要素があったとして１００×ｎ回なのと、１００×１００×ｎなのでは
後者のほうが効率が悪いですよね。

お礼

ありがとうございました