C言語　挿入ソート　計算量と合わない

c言語で配列を挿入ソートでソートするプログラムが計算量に対してが少なくなってしまいます。

c
1#include <stdio.h>
2#include <stdlib.h>
3#include <time.h>
4
5#define N  10000
6
7int ccount = 0;     
8int scount = 0;   
9
10void init(void);
11int myrand(void);
12void print(void);
13void swap(int i, int j);
14int comp(int i, int j);
15void shuffle(int array[], int size) ; //追記部分
16
17int a[N+1];     /* これで a[1] ... a[N] が使える。a[0] は使わない */
18
19int main() 
20{
21    printf("配列の大きさは %d です.  ", N);     /* 配列の大きさを出力 */
22    printf("…………栗原稔\n");             /* 自分の氏名を出力 */
23    init();                                     /* 初期化 */
24       for(int i= 0,i != 3;++i)  //追記部分　シャッフル
25    {
26        shuffle(a,N);
27    }
28    print();  //初期化した配列の確認
29    for(int i = 2; i != N + 1; ++i)
30    {
31        //printf("今からa[%d](=%02d)を挿入します\n",i,a[i]);
32        for(int j = i; j > 1 && comp(a[j - 1],a[j]) > 0; --j)
33        {
34            swap(j -1, j); 
35        }
36    }
37    printf("%d回比較しました\n",ccount);
38    printf("%d回交換しました\n",scount);
39    print();　　//ソートできているか確認
40}
41
42
43void init(void) 
44{
45    int i;
46
47    {  
48        unsigned seed = (unsigned)time(NULL);   /* 現在時刻を取得して */
49        printf("乱数の種は %u です.\n", seed);
50        srand(seed);                            /* それを乱数の種に */
51    }
52
53    a[0] = 0;                       /* 念のためこうしておく */
54
55    if (N < 80) 
56    {                   /* N が小さいとき */
57        for (i = 1; i <= N; i++) 
58        {
59            a[i] = rand() % 99  + 1;
60        }
61    } 
62    else 
63    {                        /* N を大きくして実験するとき */
64        for (i = 1; i <= N; i++) 
65        {
66            a[i] = myrand();
67        }
68    
69    }
70}
71
72
73int myrand(void) 
74{      /* 1 から 1073741824 までに値をとる乱数を返す */
75    int r;
76
77    r = rand();
78    return rand() * 32768 + r + 1;
79}
80
81
82void print(void) /*配列を書き出す*/
83{
84    for(int i = 1; i != N + 1  ; ++i)
85    {
86        printf("%2d ",a[i]);
87    }
88    printf("\n");
89}
90
91void swap(int i, int j)/*入れ替える*/
92{
93    scount++;
94    int c = a[i];
95    a[i] = a[j];
96    a[j] = c;
97    
98}
99
100int comp(int i, int j)/*比較する*/
101{
102    ccount++;
103    return i - j;
104}
105
106void shuffle(int array[], int size) {　　　　　//シャッフル　　追記部分
107    for(int i = 0; i < size; i++) {
108        int j = rand()%size;
109        int t = array[i];
110        array[i] = array[j];
111        array[j] = t;
112    }
113}

配列の初期化の確認　配列の数100

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

このプログラムの計算量はおよそ O(n^2)/2 だと考えます。
そうすると交換回数と比較回数が 2500万ぐらいにならないとおかしいはずなのに
毎回、比較は23000回　交換は12000回くらいになります。
正しくソートはされていると思います。
どうしてでしょうか？
配列の初期化の時にある程度ソートされているのでしょうか？

実行環境は
macOS Big Sur 11.6
apple m1 チップ
コンパイラ　gcc 11.2
エディタ　vscode
です

jimbe

2022/05/27 11:36

ソート結果が正しいのであれば、想定した計算量やそれに対する考え方が間違っていると推論するのが妥当ではないでしょうか。

Bull

2022/05/28 02:42

当方の環境 (Windows10, gcc) で実行した結果、ほぼ想定通りの結果になっています。挿入ソートはほぼソート済みの配列に対しては、比較回数も交換回数も少なくなります。ソート対象の配列がどのような状態なのか確認してみては如何でしょうか？

mkn66

2022/05/28 02:55

jimbeさん回答ありがとうございます。他の人にも実行してもらったんですが相応の数になり、間違っているとは考えづらいです。 Bullさん回答ありがとうございます。配列を初期化した後、Fisher-Yatesシャッフルアルゴルズムで配列を何回かシャッフルした後にソートしても少なくなってしまいソート対象の配列は関係があまりないように思います。

Bull

2022/05/28 04:38

質問のソースコードは、Fisher-Yatesシャッフルアルゴルズムは使用してないようですが、実際に実行したソースコードを投稿して貰えますか？また、ソート対象の配列はどのようにして確認しましたか。なっているはずではなく、実際に確認してみてください。

mkn66

2022/05/28 10:14

了解しました。質問文にあるソースコードに追加しました。ソート対象は自作のprint関数で確認しました。例として配列数100の初期化状態を追加しておきました。ある程度ソートされているとは考えずらいと思いました。

mkn66

2022/05/28 10:15

よろしくお願いします。

Bull

2022/05/29 01:50

乱数列の生成方法に、気になる点がいくつかありますが、本題ではないので一旦保留します。ソート前の配列がソート済みになっていることはなさそうですね。と、なると当方の環境では検証が難しいです。提案ですが、N = 10 にして、検証を行っては如何でしょうか？ N = 10 ではデータによりますが、比較は30回程度、交換は20回程度になると思われます。そのような結果にならないのであれば、想定通りに動作しているかデバッガでトレースしてみればいいです。正しい結果になるのであれば、N を増やして検証して、どこで想定外の回数になるか検証してみる価値はあるかと思います。

行動規範の内容に同意します

回答2件

私の環境(WSLのDebian、GCC)で実行したところちょうど「比較は23000回　交換は12000回くらい」に近い値になったので原因を探ってみました。
RAND_MAXが32767である前提でmyrand()が実装されていますが、私の環境のRAND_MAXは2147483647であったためmyrand()の返り値の範囲が想定された「1 から 1073741824 まで」でなくint全体になり、比較のためのi - jがオーバーフローして比較結果が正しくない場合が生じるのが原因でした。

投稿2022/11/06 09:43