Order by pair comparisons: Difference between revisions
m
→{{header|Phix}}: added 10% vs 50% initial gap note
m (→{{header|Phix}}: added 10% vs 50% initial gap note) |
|||
Line 92:
The number of questions asked is entirely dependent on how the initial order marries in with the sorting algorithm.<br>
This needs just 6 questions to handle an already in-order or only first two items swapped list.<br>
I picked an initial ordering that requires a fairly easy to remember set of answers: 4Y then alternate.<br>
The builtin sort(s) use an initial gap of 10%, ultimately balancing #comparisons against cache hits, which leads to a wider range of #questions, as said best case 6, worst case 21. A better match to the narrower range of Python (I think 10..14) could probably be made using a copy of custom_sort (it is only 52 lines) with an initial 50% gap.
<!--<lang Phix>(notonline)-->
<span style="color: #004080;">integer</span> <span style="color: #000000;">qn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
| |||