※参考情報※
ランダムな要素 10000個のコムソートに於いて、ギャップが 1 になった時点で
最大どれだけ離れているかを 1000回出してみました。
| N = 10000 |
|---|
| A | M | COMP/SWAP |
|---|
| min | max | ave | TO 1 | TOTAL |
| 1.05 | 1 | 1 | 1.0 | 1170000 | 1190000 |
| 1.10 | 1 | 1 | 1.0 | 660000 | 680000 |
| 1.15 | 1 | 2 | 1.4 | 474000 | 494000 |
| 1.20 | 1 | 3 | 1.7 | 380000 | 401000 |
| 1.25 | 2 | 5 | 3.1 | 310000 | 351000 |
| 1.30 | 4 | 10 | 6.0 | 267000 | 337000 |
| 1.35 | 7 | 157 | 16.7 | 231000 | 409000 |
| 1.40 | 21 | 1314 | 153.4 | 215000 | 1760000 |
| 1.45 | 157 | 2087 | 579.7 | 188000 | 5990000 |
| 1.50 | 458 | 2470 | 1078.5 | 180000 | 11000000 |
| bubble sort | 98700000 |
※ちなみにシェルソート(分割数 P , 1 の２段)※
| N = 10000 |
|---|
| P | SHIFTS |
|---|
| min | max | ave |
| 1 | 24400000 | 25500000 | 25000000 |
| 2 | 12300000 | 13100000 | 12600000 |
| 3 | 8330000 | 8990000 | 8580000 |
| 4 | 6350000 | 6910000 | 6570000 |
| 5 | 5140000 | 5710000 | 5390000 |
| 6 | 4370000 | 5010000 | 4610000 |
| 7 | 3820000 | 4450000 | 4070000 |
| 8 | 3440000 | 4030000 | 3670000 |
| 9 | 3080000 | 3740000 | 3360000 |
| 10 | 2900000 | 3460000 | 3120000 |
| 50 | 1780000 | 2360000 | 2030000 |
| 100 | 2180000 | 2720000 | 2440000 |
| 150 | 2520000 | 3200000 | 2850000 |
| 200 | 2960000 | 3570000 | 3250000 |
※コムソートは前処理として、挿入ソートで仕上げる※
と言う考察があったので、データを取ってみました。
| N = 10000 |
|---|
| A | COMP/SWAP/SHIFTS |
|---|
| TO 1 | LAST | TOTAL |
| 1.05 | 1170000 | 12300 | 1180000 |
| 1.10 | 660000 | 12300 | 673000 |
| 1.15 | 474000 | 12400 | 486000 |
| 1.20 | 380000 | 12400 | 393000 |
| 1.25 | 310000 | 12600 | 323000 |
| 1.30 | 267000 | 13100 | 280000 |
| 1.35 | 231000 | 15600 | 247000 |
| 1.40 | 215000 | 16500 | 232000 |
| 1.45 | 188000 | 34200 | 222000 |
| 1.50 | 180000 | 67100 | 247000 |
| 1.55 | 162000 | 158000 | 320000 |
| 1.60 | 153000 | 278000 | 432000 |
| 1.65 | 145000 | 455000 | 600000 |
| 1.70 | 136000 | 642000 | 778000 |
| inserting | 25000000 |
確かに効果はあるようですね。