Demonstration for sorting.
comparison of quicksort which 1) always uses a[0] as its pivot 71.html 2) uses the median of three a[0], a[end>>1], a[end-1] as the pivot (this page) 3) follows the quicksort7 method 167.html For n = 200 1) 1496 923 1441 900 1604 947 1513 777 1642 1050 1759 870 1577 823 1420 846 1707 1268 1545 1032 1541 751 1780 977 1573 754 1672 1226 1667 961 1751 840 1578 836 1536 746 1514 900 1480 876 1403 763 1612 688 1492 809 1630 934 1397 789 1506 889 1719 960 1568 822 1461 743 1526 820 statistic (mean, stdev) comparisons (1519.677, 300.839) swaps (855.484, 252.616) 2) 1412 728 1502 807 1540 779 1682 859 1718 1082 1510 830 1682 949 1410 776 1444 788 1404 793 1417 749 1462 952 1488 822 1432 812 1452 854 1434 772 1469 811 1542 790 1417 819 1431 731 1493 899 1531 918 1403 834 1487 854 1472 838 1431 795 1496 807 1440 780 1449 782 1663 818 comparisons(1354.939, 443.083); swaps(752.364, 251.458) 3) 2169 651 1973 604 1960 492 1984 588 2240 553 2074 533 2011 467 2105 691 2050 561 1927 546 2042 641 2185 517 1861 589 2075 558 2107 518 2233 526 2053 506 1953 437 2135 560 2057 521 1970 537 2025 567 2094 459 2131 554 2092 445 2076 579 2058 573 2042 656 2137 566 2070 592 comparisons(1820.26, 607.885) swaps(502.636, 171.501)
Which sorting function to use depends on the cost associated with the basic operations: compare() and swap(). In some cases, a swap may be cheaper (like when JavaScript must evaluate a user-specified function for each comparison). In most raw cases, comparisons are cheaper; but the world is getting less and less "raw" with the advent of encapsulated programming.
Since the costs of compare() and swap() are relative to each other, we may assume that a comparison has a constant cost of 1. Then we can determine for what relative cost of swapping one of the three ways might have an advantage. In general, the median-of-three technique reduces both the number of comparisons (by 10.84%) and the number of swaps (by 12.05%). The quicksort7 technique tends to increase the number of comparisons quite a bit (by 19.78%) and also reduce the number of swaps a very large amount (by 41.25%).
The cost equation is
C = 1*1519.677*rel_compares + A*855.484*rel_swaps
Since both its swaps and comparisons are lower, it always has better probability to use method 2) than method 1). Whether we should use quicksort7 depends on the value of A.
Thus, we need to determine the cost of method 2 and 3, and solve for A where they are equal. Any larger value of A means that quicksort7 is more efficient; any smaller value means it is not.
Cost of 2 = 1*1519.677*.8916 + A*855.484*.8795 Cost of 3 = 1*1519.677*1.1978 + A*855.484*.5875 ----> Let Cost of 2 = Cost of 3 1*1519.677*.8916 + A*855.484*.8795 = 1*1519.677*1.1978 + A*855.484*.5875 A(855.484*.8795 - 855.484*.5875) = 1*1519.677*1.1978 - 1*1519.677*.8916 A = (1*1519.677*1.1978 - 1*1519.677*.8916) / (855.484*.8795 - 855.484*.5875) A = 1.863
Thus, whenever it costs at least twice as much to swap as to make a comparison, quicksort7 should be used. Otherwise, it is safest to use the median-of-three technique.