#!/bin/sh # # Compare quick_asymm.c and quick_random.c # # -h : quicksort with a pivot Hole. # -a : simple Asymmetric quicksort. # -r : quick sort with a random pivot hole. # -P l,m,n,o : threshold to change the choice of Pivot. # N <= l -- middle element. # N <= m -- median of 3 elements. # else -- median of (log2(N)/2)|1 elements. # if [ $# -eq 0 ]; then echo "Usage : $0 Number [data_file]" else N=$1; shift Release/Sort -N $N -Z 16 -3hq $* fi exit The following lines after @ are appended by a scirpt "performance". start : Wed Jun 21 08:12:12 UTC 2017 computer : archiso 4.8.6-1-ARCH #1 SMP PREEMPT Mon Oct 31 18:51:30 CET 2016 unknown GNU/Linux operator : root option : asymmetric 26 20 stop : Wed Jun 21 20:30:19 UTC 2017 1 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 650 1396 3064 6473 14273 29724 65370 139161 295085 628773 1322368 2688295 5637686 11878279 24693872 qsort_med3() 668 1425 3065 7049 14411 29665 66636 138682 296954 625764 1188503 2527226 5195797 10911674 22753890 quick_hole() 616 1381 2838 6115 13412 28158 61300 132013 275731 565212 1161378 2451731 5115040 10957070 22589402 asymm_qsort() 603 1341 2768 6079 12974 27526 58126 126358 267287 549906 1139544 2368549 5003637 10461346 21689633 2 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 1152 1390 3158 6794 14234 30155 65153 137859 295298 629002 1314867 2754807 5664299 11774439 24664578 qsort_med3() 663 1424 3159 6835 14444 31162 66344 140445 298302 629274 1241765 2560492 5226216 11227940 22618410 quick_hole() 621 1330 3095 6436 13661 29090 61442 129916 276386 576875 1184607 2480686 5176676 10757966 22829189 asymm_qsort() 610 1314 3052 6360 12851 28333 58694 126605 266990 565077 1150047 2376010 4979887 10522096 21689859 3 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 644 1461 3154 6434 14463 30728 63454 139168 295398 623822 1307060 2693008 5676149 11782359 24594184 qsort_med3() 746 1480 3194 6536 14483 31017 60574 139618 298787 578514 1220653 2558572 5386255 10945085 22655107 quick_hole() 610 1380 3057 6135 13351 28941 58325 129318 272444 565678 1172283 2496612 5227996 10911807 22556614 asymm_qsort() 613 1365 2974 6105 13357 27557 56836 126680 257632 549257 1139026 2381895 5100729 10418033 21692279 4 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 653 1422 3080 6540 14399 31119 65250 138841 293784 629662 1305991 2705829 5631620 11821124 24662426 qsort_med3() 666 1435 3182 6567 14552 31625 65376 131214 275459 561903 1241404 2494667 5493339 10928097 22750422 quick_hole() 616 1366 3005 6143 13948 28867 61200 127302 268059 548942 1195707 2480108 5233085 11033400 23100843 asymm_qsort() 609 1342 2867 6080 13274 28534 59764 123618 258994 540937 1130127 2375562 4985148 10405793 21704970 5 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 640 1407 3270 6434 14366 30867 63293 139436 293711 630766 1293948 2728182 5648166 12011076 24683414 qsort_med3() 664 1437 3215 6525 14518 31371 63177 132945 293420 586710 1203066 2622171 5351414 11181305 22697099 quick_hole() 628 1358 3022 6089 13571 29429 61783 125541 272719 582788 1211083 2505224 5181077 10984026 22524483 asymm_qsort() 607 1342 2936 6084 13289 27831 58044 122545 267272 545297 1131206 2414156 4969410 10524394 21842429 6 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 651 1408 3138 6598 14442 30803 63288 138903 293897 629967 1305038 2723436 5727000 11843401 24696052 qsort_med3() 664 1432 3290 6626 14455 31498 63079 141337 297342 582264 1236088 2495968 5205082 10959366 22576526 quick_hole() 605 1361 2985 6202 13330 29465 61039 130516 274117 571018 1192408 2427918 5165118 10835307 22532872 asymm_qsort() 596 1330 2928 6053 12913 28620 58138 127173 254444 550094 1145753 2372687 4979058 10397852 21731153 7 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 650 1412 3071 6536 14233 29881 65313 138080 294698 629947 1324029 2699716 5653571 11809180 24708886 qsort_med3() 664 1431 3200 6574 14641 30426 66670 132019 275915 615800 1320107 2557800 5464557 11406844 23336407 quick_hole() 615 1336 2991 6217 13758 28032 60265 127925 270720 578863 1210913 2475663 5218004 10805660 22604708 asymm_qsort() 608 1336 2933 6056 13344 27541 58450 122350 258998 563470 1160160 2374309 4968717 10415269 21661724 8 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 1184 1424 3033 6511 13943 30848 63483 139202 294179 623866 1283105 2778748 5696754 11832049 24729004 qsort_med3() 688 1443 3079 6585 13971 31038 63453 140631 277718 583013 1219488 2565444 5461688 11203972 23343130 quick_hole() 635 1427 2860 6229 13651 29121 61036 130696 261995 561953 1207566 2454368 5293152 10902468 22772607 asymm_qsort() 630 1336 2868 6087 13041 28436 58172 126280 255038 540724 1156519 2394494 4981787 10423348 21729927 9 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 1180 1461 3189 6552 14026 30581 64294 139244 289102 618073 1326751 2688834 5629729 11825495 24711574 qsort_med3() 667 1488 3064 6601 13886 31127 60051 141876 281975 583367 1314452 2548643 5457532 10890147 22635825 quick_hole() 617 1395 2871 6111 13290 29304 59222 131005 269405 564279 1210586 2453272 5181731 10755230 23167353 asymm_qsort() 610 1472 2874 6073 12906 28562 56807 126421 258934 545929 1184793 2392357 4979714 10400441 21737476 10 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 648 1425 3157 6843 14570 29960 62904 139642 294661 607160 1290123 2759314 5641966 11837548 24614831 qsort_med3() 688 1584 3094 6786 14485 29763 63096 141690 276251 580718 1224969 2556513 5363717 10850810 22699945 quick_hole() 627 1368 2859 6212 13981 28158 59940 126971 265879 568771 1178297 2455096 5140630 10780353 22697530 asymm_qsort() 617 1366 2862 6035 13327 27808 58119 124367 254081 545593 1128750 2368766 5024308 10477262 21732959 11 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 651 1395 3039 6639 14443 29904 65253 139431 294287 629448 1325826 2705686 5673856 11832608 24682954 qsort_med3() 669 1440 3108 6798 14390 29770 62518 140982 296730 617123 1323626 2505709 5213554 10956298 22663586 quick_hole() 619 1294 2878 6432 13671 28240 61216 129781 274173 578564 1206094 2468946 5221779 10730185 22429117 asymm_qsort() 612 1289 2862 6241 13587 27647 58282 126722 268110 563183 1165284 2373279 4974178 10386403 21679849 12 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 653 1388 3163 6532 14127 29875 64237 138934 294512 628118 1284981 2703154 5748268 11826552 24648891 qsort_med3() 693 1434 3192 6606 14551 29865 67045 141183 296782 579303 1185530 2567894 5350164 10896810 23347303 quick_hole() 643 1357 2943 6174 13873 28568 62471 124910 271888 554438 1185983 2463903 5221491 10716776 22604555 asymm_qsort() 627 1339 2936 6060 13471 27664 59888 123373 267294 538692 1128813 2399021 5023931 10407620 21900025 13 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 652 1460 3193 6820 14281 30741 65116 134180 289999 622568 1285656 2704458 5655600 11802380 24608757 qsort_med3() 664 1495 3260 6856 14410 31260 65610 131628 276681 581764 1197193 2497232 5208167 11148642 23725622 quick_hole() 633 1381 3078 6443 13546 29150 62232 126227 263746 567451 1162706 2521083 5207498 10860666 22957005 asymm_qsort() 606 1375 2872 6230 13250 28436 60032 123155 258655 549353 1129518 2370741 4969844 10392709 21718078 14 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 680 1475 3116 6756 14575 29893 62736 139117 294573 625994 1305498 2697642 5615218 11789616 24629114 qsort_med3() 689 1487 3057 6778 14468 30242 60226 141486 293362 625079 1215094 2492920 5373857 10907341 22892249 quick_hole() 627 1366 2968 6265 13555 28126 57963 131574 269311 584947 1183569 2519757 5196348 10738613 22745170 asymm_qsort() 628 1347 2854 6256 13311 27609 57430 126281 258916 562655 1129791 2366484 4975146 10420896 21750206 15 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 654 1437 3153 6743 14420 30795 65659 134371 294354 629214 1304948 2679905 5616742 11808946 24561925 qsort_med3() 678 1486 3196 6821 14548 31254 59828 126836 297825 580107 1218144 2608647 5262821 11141951 22752962 quick_hole() 634 1369 3002 6277 13524 29026 58673 123772 272618 561496 1185215 2507412 5148989 10882237 22662626 asymm_qsort() 609 1397 3163 6251 13511 28674 56831 121345 268536 545792 1149156 2414346 5022781 10480589 21698520 16 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 645 1460 3248 6759 14334 31004 65254 138920 294743 629508 1323942 2753169 5632962 11865362 24707604 qsort_med3() 667 1484 3190 6795 14536 29919 60304 138407 276787 627439 1294515 2574123 5373857 10919357 22542880 quick_hole() 640 1367 3024 6306 13451 28404 58631 130090 266802 579734 1221943 2462939 5286522 10771782 22458399 asymm_qsort() 613 1384 2889 6051 13275 27722 57386 126275 260962 562803 1184976 2376410 4973222 10406940 21627900 17 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 654 1415 3157 6710 13773 30922 65244 139918 291376 630193 1324120 2707440 5676444 11838894 24629057 qsort_med3() 667 1452 3190 6891 13915 28499 65820 139712 276453 592869 1214715 2492851 5363654 10931848 22661524 quick_hole() 630 1339 3144 6436 12858 27823 61351 129365 265830 567087 1180359 2494472 5144417 10695423 22475347 asymm_qsort() 614 1342 2945 6267 12855 26986 60091 123778 260446 536811 1147019 2390662 4970646 10397372 21898873 18 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 671 1438 3155 6660 14333 30937 65440 139190 293882 629401 1323061 2692285 5698414 11902132 24650686 qsort_med3() 686 1489 3148 6562 14458 31089 65958 140084 279255 616428 1296963 2596178 5366653 10890738 23011730 quick_hole() 645 1421 2952 6299 13490 29140 61622 131241 272010 576847 1213019 2502400 5215791 10825848 23030191 asymm_qsort() 627 1368 2942 6073 13360 28681 60287 125818 258773 562925 1158044 2392332 4974135 10402533 21675726 19 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 646 1470 3046 6620 13906 30898 63141 138775 294117 631409 1313986 2712602 5658757 11865984 24718043 qsort_med3() 649 1479 3101 6583 14162 31112 62691 140556 299342 583486 1223447 2490691 5292127 11173803 22709130 quick_hole() 610 1435 2955 6170 13162 28827 59021 131390 275822 569422 1180672 2445060 5153912 11033254 22756845 asymm_qsort() 602 1375 2871 6031 12989 28473 57465 126457 266954 553148 1128674 2399011 4978801 10508727 21705869 20 log2(N) 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 qsort(3) 652 1462 3102 6782 14130 29737 62972 138791 295250 629089 1290472 2762106 5629061 11842714 24665109 qsort_med3() 662 1481 3188 6791 13898 31208 64817 140560 296685 623551 1245469 2487609 5360679 11198616 22656017 quick_hole() 617 1393 3047 6342 13053 28001 59063 131474 276389 565797 1180952 2449816 5192741 10862501 23029296 asymm_qsort() 608 1392 2968 6619 12951 27775 57993 127067 263367 554354 1127899 2371612 5013078 10504871 21720043 @