** 玄箱HG(PowerPC 266MHz) debian4(etch) 環境 gcc v4.1.2 でコンパイル(-O2 -DNDEBUG) タイマーの精度はあまりよくない(4ミリ秒単位くらい?) *** int (4bytes) の SORT テスト , 個数 , 10個, 20個, 30個, 40個, 50個, 64個, 100個, 128個, 256個, 512個, 1024個, 10000個, 100000個, 1000000個, , 回数(結果は平均) , (10000回), ( 5000回), ( 3333回), ( 2500回), ( 2000回), ( 1562回), ( 1000回), ( 781回), ( 390回), ( 195回), ( 98回), ( 10回), ( 1回), ( 1回), ,バブル SORT , 2.000, 7.200, 15.602, 25.600, 40.000, 64.020, 156.000, 256.082, 1015.385, 4061.538, 16163.265, 2085600.000, ---, ---, ,挿入 SORT , 1.600, 4.000, 8.401, 12.800, 22.000, 33.291, 76.000, 117.798, 461.538, 1805.128, 7102.041, 815200.000, ---, ---, ,挿入 SORT (yane) , 1.200, 3.200, 7.201, 11.200, 18.000, 28.169, 64.000, 102.433, 389.744, 1558.974, 6040.816, 729200.000, ---, ---, ,シェル SORT , 2.000, 4.000, 7.201, 11.200, 16.000, 23.047, 40.000, 56.338, 133.333, 307.692, 734.694, 13200.000, 216000.000, 3612000.000, ,コム SORT , 2.000, 4.800, 8.401, 12.800, 16.000, 25.608, 44.000, 61.460, 143.590, 328.205, 775.510, 16000.000, 196000.000, 2556000.000, ,QUICK SORT(単純) , 3.200, 7.200, 10.801, 14.400, 20.000, 28.169, 44.000, 56.338, 123.077, 287.179, 571.429, 7200.000, 88000.000, 1064000.000, ,QUICK SORT(+挿入) , 1.200, 4.000, 7.201, 9.600, 12.000, 15.365, 28.000, 35.851, 82.051, 184.615, 367.347, 5600.000, 64000.000, 836000.000, ,QUICK SORT(+yane) , 1.200, 4.000, 7.201, 9.600, 12.000, 17.926, 28.000, 40.973, 82.051, 184.615, 408.163, 6000.000, 68000.000, 844000.000, ,std::sort , 2.000, 4.000, 6.001, 8.000, 12.000, 15.365, 24.000, 35.851, 71.795, 164.103, 367.347, 5600.000, 60000.000, 768000.000, ,std::stable_sort , 5.200, 12.000, 15.602, 19.200, 22.000, 33.291, 48.000, 66.581, 133.333, 287.179, 612.245, 10800.000, 128000.000, 1592000.000, ,マージ SORT , 1.200, 4.000, 7.201, 12.800, 16.000, 17.926, 36.000, 40.973, 102.564, 205.128, 448.980, 7600.000, 96000.000, 1344000.000, ,基数 SORT , 42.000, 45.600, 48.005, 51.200, 54.000, 56.338, 68.000, 76.825, 112.821, 184.615, 285.714, 4400.000, 72000.000, 1024000.000, ,multiset insert , 22.400, 45.600, 68.407, 92.800, 116.000, 148.528, 236.000, 302.177, 615.385, 1271.795, 2897.959, 45200.000, 680000.000, ---, ,vector insert , 7.600, 16.800, 25.203, 35.200, 44.000, 58.899, 100.000, 143.406, 369.231, 1005.128, 3142.857, 385200.000, ---, ---, *** double (8bytes) の SORT テスト , 個数 , 10個, 20個, 30個, 40個, 50個, 64個, 100個, 128個, 256個, 512個, 1024個, 10000個, 100000個, 1000000個, , 回数(結果は平均) , (10000回), ( 5000回), ( 3333回), ( 2500回), ( 2000回), ( 1562回), ( 1000回), ( 781回), ( 390回), ( 195回), ( 98回), ( 10回), ( 1回), ( 1回), ,バブル SORT , 2.800, 11.200, 22.802, 40.000, 62.000, 104.994, 256.000, 414.853, 1651.282, 6564.103, 26285.714, ---, ---, ---, ,挿入 SORT , 2.000, 5.600, 12.001, 19.200, 30.000, 48.656, 108.000, 179.257, 676.923, 2666.667, 10530.612, ---, ---, ---, ,挿入 SORT (yane) , 1.600, 5.600, 10.801, 19.200, 28.000, 46.095, 104.000, 169.014, 646.154, 2564.103, 10163.265, ---, ---, ---, ,シェル SORT , 2.000, 6.400, 9.601, 16.000, 20.000, 28.169, 52.000, 71.703, 174.359, 410.256, 938.776, 18000.000, 312000.000, 5452000.000, ,コム SORT , 2.400, 7.200, 12.001, 19.200, 24.000, 33.291, 64.000, 92.190, 215.385, 492.308, 1142.857, 25200.000, 320000.000, 4216000.000, ,QUICK SORT(単純) , 4.000, 8.800, 13.201, 20.800, 26.000, 35.851, 56.000, 71.703, 164.103, 348.718, 775.510, 10000.000, 124000.000, 1524000.000, ,QUICK SORT(+挿入) , 1.600, 5.600, 10.801, 12.800, 18.000, 23.047, 36.000, 51.216, 123.077, 246.154, 571.429, 7600.000, 100000.000, 1248000.000, ,QUICK SORT(+yane) , 1.600, 5.600, 12.001, 12.800, 18.000, 23.047, 40.000, 56.338, 112.821, 266.667, 571.429, 7200.000, 96000.000, 1240000.000, ,std::sort , 2.400, 6.400, 9.601, 12.800, 18.000, 20.487, 36.000, 46.095, 102.564, 225.641, 489.796, 6800.000, 88000.000, 1128000.000, ,std::stable_sort , 6.400, 12.800, 19.202, 22.400, 26.000, 40.973, 60.000, 81.946, 174.359, 369.231, 816.327, 15600.000, 200000.000, 2452000.000, ,マージ SORT , 2.000, 5.600, 12.001, 19.200, 22.000, 25.608, 48.000, 61.460, 123.077, 287.179, 612.245, 10800.000, 156000.000, 2120000.000, ,基数 SORT , 89.600, 97.600, 105.611, 113.600, 122.000, 130.602, 160.000, 184.379, 287.179, 492.308, 979.592, 14400.000, 180000.000, 2080000.000, ,multiset insert , 22.800, 46.400, 70.807, 96.000, 120.000, 153.649, 244.000, 317.542, 646.154, 1415.385, 3183.673, 47200.000, ---, ---, ,vector insert , 8.800, 17.600, 28.803, 40.000, 54.000, 71.703, 132.000, 189.501, 523.077, 1620.513, 5469.388, ---, ---, ---, *** SmpClass (8bytes) の SORT テスト , 個数 , 10個, 20個, 30個, 40個, 50個, 64個, 100個, 128個, 256個, 512個, 1024個, 10000個, 100000個, 1000000個, , 回数(結果は平均) , (10000回), ( 5000回), ( 3333回), ( 2500回), ( 2000回), ( 1562回), ( 1000回), ( 781回), ( 390回), ( 195回), ( 98回), ( 10回), ( 1回), ( 1回), ,バブル SORT , 2.800, 10.400, 24.002, 41.600, 64.000, 102.433, 248.000, 409.731, 1620.513, 6502.564, 25959.184, ---, ---, ---, ,挿入 SORT , 2.400, 7.200, 14.401, 24.000, 38.000, 58.899, 132.000, 215.109, 830.769, 3241.026, 12897.959, ---, ---, ---, ,挿入 SORT (yane) , 2.000, 6.400, 13.201, 22.400, 34.000, 56.338, 132.000, 209.987, 820.513, 3241.026, 12857.143, ---, ---, ---, ,シェル SORT , 2.400, 6.400, 12.001, 19.200, 22.000, 30.730, 60.000, 81.946, 194.872, 451.282, 1102.041, 20400.000, 360000.000, 6328000.000, ,コム SORT , 2.800, 8.000, 13.201, 19.200, 26.000, 35.851, 64.000, 92.190, 225.641, 512.821, 1183.673, 26000.000, 336000.000, 4336000.000, ,QUICK SORT(単純) , 4.000, 8.800, 14.401, 20.800, 26.000, 35.851, 60.000, 76.825, 174.359, 369.231, 816.327, 10400.000, 128000.000, 1608000.000, ,QUICK SORT(+挿入) , 1.600, 5.600, 12.001, 14.400, 20.000, 23.047, 40.000, 56.338, 123.077, 266.667, 571.429, 7600.000, 104000.000, 1292000.000, ,QUICK SORT(+yane) , 2.000, 6.400, 12.001, 14.400, 18.000, 23.047, 44.000, 56.338, 123.077, 266.667, 612.245, 8000.000, 104000.000, 1300000.000, ,std::sort , 2.400, 6.400, 10.801, 14.400, 18.000, 25.608, 40.000, 51.216, 123.077, 266.667, 571.429, 8000.000, 100000.000, 1256000.000, ,std::stable_sort , 5.600, 11.200, 15.602, 20.800, 24.000, 35.851, 56.000, 71.703, 164.103, 348.718, 734.694, 15200.000, 200000.000, 2432000.000, ,マージ SORT , 2.000, 5.600, 10.801, 19.200, 24.000, 28.169, 48.000, 61.460, 133.333, 307.692, 693.878, 11600.000, 172000.000, 2244000.000, ,基数 SORT , 42.800, 46.400, 50.405, 52.800, 56.000, 58.899, 76.000, 81.946, 133.333, 205.128, 448.980, 7200.000, 104000.000, 1244000.000, ,multiset insert , 23.200, 47.200, 70.807, 96.000, 120.000, 156.210, 244.000, 322.663, 656.410, 1415.385, 3183.673, 46400.000, ---, ---, ,vector insert , 7.200, 14.400, 24.002, 35.200, 46.000, 66.581, 120.000, 179.257, 543.590, 1805.128, 6489.796, ---, ---, ---, *** SmpClass* (4bytes) の SORT テスト , 個数 , 10個, 20個, 30個, 40個, 50個, 64個, 100個, 128個, 256個, 512個, 1024個, 10000個, 100000個, , 回数(結果は平均) , (10000回), ( 5000回), ( 3333回), ( 2500回), ( 2000回), ( 1562回), ( 1000回), ( 781回), ( 390回), ( 195回), ( 98回), ( 10回), ( 1回), ,バブル SORT , 4.000, 13.600, 28.803, 49.600, 76.000, 125.480, 296.000, 486.556, 1897.436, 10174.359, 75469.388, ---, ---, ,挿入 SORT , 3.200, 8.800, 16.802, 27.200, 40.000, 61.460, 140.000, 225.352, 841.026, 3610.256, 27306.122, ---, ---, ,挿入 SORT (yane) , 2.800, 8.000, 15.602, 25.600, 38.000, 56.338, 132.000, 204.866, 789.744, 3446.154, 26938.776, ---, ---, ,シェル SORT , 3.600, 8.000, 14.401, 22.400, 28.000, 35.851, 64.000, 87.068, 205.128, 615.385, 1877.551, 66800.000, 1496000.000, ,コム SORT , 3.600, 9.600, 16.802, 25.600, 34.000, 46.095, 84.000, 112.676, 266.667, 1230.769, 4448.980, 148000.000, 2460000.000, ,QUICK SORT(単純) , 5.200, 11.200, 19.202, 24.000, 34.000, 43.534, 72.000, 92.190, 205.128, 471.795, 1224.490, 29600.000, 504000.000, ,QUICK SORT(+挿入) , 3.200, 8.800, 16.802, 19.200, 26.000, 33.291, 56.000, 76.825, 164.103, 389.744, 979.592, 27200.000, 484000.000, ,QUICK SORT(+yane) , 2.800, 8.000, 16.802, 19.200, 26.000, 33.291, 56.000, 76.825, 153.846, 369.231, 1020.408, 27200.000, 484000.000, ,std::sort , 4.000, 8.000, 13.201, 17.600, 24.000, 30.730, 44.000, 61.460, 133.333, 328.205, 938.776, 26800.000, 468000.000, ,std::stable_sort , 7.600, 16.800, 22.802, 28.800, 34.000, 48.656, 72.000, 102.433, 215.385, 492.308, 1714.286, 30400.000, 444000.000, ,マージ SORT , 2.800, 8.800, 16.802, 25.600, 30.000, 35.851, 64.000, 81.946, 174.359, 430.769, 1061.224, 21600.000, 368000.000, ,基数 SORT , 44.000, 48.800, 52.805, 57.600, 62.000, 69.142, 84.000, 97.311, 164.103, 451.282, 1306.122, 24800.000, 344000.000, ,multiset insert , 24.000, 49.600, 75.608, 100.800, 128.000, 166.453, 260.000, 343.150, 707.692, 1579.487, 3918.367, 78000.000, ---, ,vector insert , 9.200, 20.000, 31.203, 43.200, 56.000, 74.264, 128.000, 169.014, 430.769, 1189.744, 3673.469, ---, ---, *** SmpClass (128bytes) の SORT テスト , 個数 , 10個, 20個, 30個, 40個, 50個, 64個, 100個, 128個, 256個, 512個, 1024個, 10000個, 100000個, , 回数(結果は平均) , (10000回), ( 5000回), ( 3333回), ( 2500回), ( 2000回), ( 1562回), ( 1000回), ( 781回), ( 390回), ( 195回), ( 98回), ( 10回), ( 1回), ,バブル SORT , 25.600, 97.600, 216.022, 380.800, 588.000, 965.429, 2332.000, 3841.229, 22071.795, 98953.846, ---, ---, ---, ,挿入 SORT , 52.800, 176.000, 369.637, 632.000, 960.000, 1549.296, 3648.000, 5961.588, 25692.308, 112000.000, ---, ---, ---, ,挿入 SORT (yane) , 50.000, 172.800, 366.037, 627.200, 954.000, 1544.174, 3640.000, 5956.466, 25723.077, 112389.744, ---, ---, ---, ,シェル SORT , 25.200, 56.800, 109.211, 179.200, 190.000, 271.447, 524.000, 645.327, 2082.051, 5066.667, 13306.122, 228000.000, 4336000.000, ,コム SORT , 15.600, 40.800, 72.007, 105.600, 138.000, 192.061, 340.000, 471.191, 1866.667, 4841.026, 11632.653, 175600.000, 2268000.000, ,QUICK SORT(単純) , 32.800, 72.800, 115.212, 158.400, 202.000, 266.325, 440.000, 588.988, 1312.821, 2933.333, 6448.980, 82000.000, 1008000.000, ,QUICK SORT(+挿入) , 52.400, 174.400, 367.237, 377.600, 478.000, 619.718, 984.000, 1280.410, 2707.692, 5661.538, 12000.000, 135600.000, 1544000.000, ,QUICK SORT(+yane) , 48.800, 170.400, 362.436, 369.600, 466.000, 601.793, 956.000, 1249.680, 2646.154, 5517.949, 11755.102, 132800.000, 1516000.000, ,std::sort , 56.800, 130.400, 200.420, 267.200, 336.000, 435.339, 692.000, 901.408, 1989.744, 4246.154, 9102.041, 108000.000, 1264000.000, ,std::stable_sort , 66.800, 191.200, 295.230, 398.400, 496.000, 819.462, 1404.000, 1895.006, 5723.077, 11466.667, 27591.837, 314000.000, 4028000.000, ,マージ SORT , 52.400, 175.200, 366.037, 625.600, 638.000, 752.881, 1540.000, 1895.006, 4646.154, 10994.872, 25346.939, 365600.000, 4876000.000, ,基数 SORT , 104.400, 168.000, 232.823, 307.200, 386.000, 501.921, 956.000, 1270.166, 2646.154, 5333.333, 10571.429, 107600.000, 1096000.000, ,multiset insert , 50.000, 100.000, 151.215, 208.000, 264.000, 363.636, 656.000, 860.435, 1815.385, 3774.359, 8122.449, ---, ---, ,vector insert , 64.000, 195.200, 397.240, 667.200, 1006.000, 1613.316, 3804.000, 6166.453, 26164.103, 112348.718, ---, ---, ---,