質問編集履歴
3
修正
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -115,6 +115,11 @@
|
|
|
115
115
|
}
|
|
116
116
|
}
|
|
117
117
|
```
|
|
118
|
+
|
|
119
|
+
配列の初期化の確認 配列の数100
|
|
120
|
+
```ここに言語を入力
|
|
121
|
+
700282416 1897966524 -2100725484 -1876004846 -1696180688 -1474562185 0 136276921 1264362763 1339367595 1666563862 1730110660 1760165765 2122186534 -2132922136 -1488817135 -1473116387 -758690103 -710010392 -698259263 -418361524 114111843 136231460 564226793 1960868995 2011546268 -1684596489 -667550689 868695254 1253769412 1384011132 -1625506819 -182599639 439962703 -1818948491 -476485698 -329722803 -277143449 493147061 610612223 788657272 902898982 1276709206 1299611947 1700983331 1731658862 -1815366202 -156710155 1832361283 -1513092376 -73157691 465106449 -2143457362 -2044619119 -1872156200 -1448762897 -1123408995 -749032840 -501729201 -298927338 -193586748 60682277 1117892438 -1777833834 -1431847031 -367295633 309240977 1068002596 1399761294 1505734092 -1949996731 -1750849005 -1517945276 -1235720067 -108140972 -79105377 959488910 1175201566 2126432167 -1964077408 -1752262400 -504991691 -41946136 -25435275 12302834 57512750 84029081 244628175 641950718 673738756 838978873 861094952 954037981 1038890199 1413205339 1726587102 -2092082101 -1156993016 -138456955 502155787
|
|
122
|
+
```
|
|
118
123
|
このプログラムの計算量はおよそ O(n^2)/2 だと考えます。
|
|
119
124
|
そうすると交換回数と比較回数が 2500万ぐらいにならないとおかしいはずなのに
|
|
120
125
|
毎回、比較は23000回 交換は12000回くらいになります。
|
2
追記依頼のため
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -15,6 +15,7 @@
|
|
|
15
15
|
void print(void);
|
|
16
16
|
void swap(int i, int j);
|
|
17
17
|
int comp(int i, int j);
|
|
18
|
+
void shuffle(int array[], int size) ; //追記部分
|
|
18
19
|
|
|
19
20
|
int a[N+1]; /* これで a[1] ... a[N] が使える。a[0] は使わない */
|
|
20
21
|
|
|
@@ -23,7 +24,11 @@
|
|
|
23
24
|
printf("配列の大きさは %d です. ", N); /* 配列の大きさを出力 */
|
|
24
25
|
printf("…………栗原稔\n"); /* 自分の氏名を出力 */
|
|
25
26
|
init(); /* 初期化 */
|
|
27
|
+
for(int i= 0,i != 3;++i) //追記部分 シャッフル
|
|
28
|
+
{
|
|
29
|
+
shuffle(a,N);
|
|
30
|
+
}
|
|
26
|
-
|
|
31
|
+
print(); //初期化した配列の確認
|
|
27
32
|
for(int i = 2; i != N + 1; ++i)
|
|
28
33
|
{
|
|
29
34
|
//printf("今からa[%d](=%02d)を挿入します\n",i,a[i]);
|
|
@@ -34,7 +39,7 @@
|
|
|
34
39
|
}
|
|
35
40
|
printf("%d回比較しました\n",ccount);
|
|
36
41
|
printf("%d回交換しました\n",scount);
|
|
37
|
-
|
|
42
|
+
print(); //ソートできているか確認
|
|
38
43
|
}
|
|
39
44
|
|
|
40
45
|
|
|
@@ -100,6 +105,15 @@
|
|
|
100
105
|
ccount++;
|
|
101
106
|
return i - j;
|
|
102
107
|
}
|
|
108
|
+
|
|
109
|
+
void shuffle(int array[], int size) { //シャッフル 追記部分
|
|
110
|
+
for(int i = 0; i < size; i++) {
|
|
111
|
+
int j = rand()%size;
|
|
112
|
+
int t = array[i];
|
|
113
|
+
array[i] = array[j];
|
|
114
|
+
array[j] = t;
|
|
115
|
+
}
|
|
116
|
+
}
|
|
103
117
|
```
|
|
104
118
|
このプログラムの計算量はおよそ O(n^2)/2 だと考えます。
|
|
105
119
|
そうすると交換回数と比較回数が 2500万ぐらいにならないとおかしいはずなのに
|
1
追加情報
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -108,5 +108,13 @@
|
|
|
108
108
|
どうしてでしょうか？
|
|
109
109
|
配列の初期化の時にある程度ソートされているのでしょうか？
|
|
110
110
|
|
|
111
|
+
実行環境は
|
|
112
|
+
macOS Big Sur 11.6
|
|
113
|
+
apple m1 チップ
|
|
114
|
+
コンパイラ gcc 11.2
|
|
115
|
+
エディタ vscode
|
|
116
|
+
です
|
|
111
117
|
|
|
112
118
|
|
|
119
|
+
|
|
120
|
+
|