私は基本的にサイズから10個のランダムな配列を作成します:8000,16000,32000,64000,128000,256000
つまり、サイズ 8000 の 10 個の配列、サイズ 16000 の 10 個の配列などがあります。
これらにはすべて、0 から配列サイズまでの範囲の乱数が取り込まれます。
シェルソートの実装があります:
public static void sortMyArray(int[] a){
for (int gap = a.length / 2; gap > 0; gap = (gap / 2)) {
for (int i = gap; i < a.length; i++) {
int tmp = a[i];
int j = i;
for (; j >= gap && tmp < (a[j - gap]); j -= gap) {
a[j] = a[j - gap];
}
a[j] = tmp;
}
}
}
ギャップがgap = a.length / aの場合。長さ 私は単に挿入ソートを持っています。これらの配列をソートする時間は次のとおりです。
Number of Elements Milliseconds
8000 13
16000 53
32000 217
64000 828
128000 3311
256000 13352
つまり、これはおおよそ O(N^2) です。要素数が 2 倍になると、解決時間はほぼ 4 倍になります。
ただし、 gap = a.length / 2 を使用すると、次のような値が得られます。
Number of Elements Milliseconds
8000 2
16000 2
32000 4
64000 10
128000 25
256000 60
これは O(N) よりも優れていると思いますか? これはどのように可能ですか?Windows からプロセッサをシャットダウンしようとしました。また、コンピュータを 1 つのプロセッサだけで実行しようとしましたが、値はまだ論理的ではありませんでした。
興味がある場合は、私の完全なコードを次に示します。
int[] arraySizes = new int[]{8000,16000,32000,64000,128000,256000};
Random rn = new Random(1);
for(int i=0;i<arraySizes.length;i++){
int[] arrayToBeSorted = new int[arraySizes[i]];
System.out.println("Solving array with: " + arraySizes[i] + " elements with first sorting algorithm.");
for (int c = 0; c < 10; c++) {
for(int t=0;t<arraySizes[i];t++){
int randomNumber = rn.nextInt(arrayToBeSorted.length);
arrayToBeSorted[t] = randomNumber;
}
Long initialTime = (new Date().getTime());
sortMyArray(arrayToBeSorted);
Long finalTime = (new Date().getTime());
System.out.println("Time in milliseconds:" + (finalTime - initialTime));
}
}