sortcount.py

# A quick test whipped up to compare HostileFork's results for C++ in his
# <<"Psychic" Sorting Algorithms>> article
# (http://blog.hostilefork.com/psychic-sorting-algorithms/) with Python.


import functools


SETUP = [
    # Exact number of comparisons per https://oeis.org/A036604,
    #    Number of comparisions required by @HostileFork's C++ test
    #        List of numbers used by @HostileFork's C++ test
    ( 0,  0, [383]),
    ( 1,  1, [386, 277]),
    ( 3,  4, [415, 293, 335]),
    ( 5,  6, [386, 492, 149, 421]),
    ( 7, 11, [362,  27, 190,  59, 263]),
    (10, 16, [426,  40, 426, 172, 236, 211]),
    (13, 18, [368,  67, 429, 282,  30, 362, 123]),
    (16, 23, [ 67, 135, 429, 302,  22,  58,  69, 167]),
    (19, 29, [393, 456,  11,  42, 229, 373, 421, 419, 284]),
    (22, 24, [ 37, 198, 324, 315, 370, 413,  26,  91, 480, 456]),
    (26, 31, [373, 362, 170, 496, 281, 305, 425,  84, 327, 336,   5]),
    (30, 26, [346, 229, 313, 357, 124, 395,  82,  45, 314, 367, 434, 364]),
    (34, 47, [ 43, 250,  87, 308, 276, 178, 288,  84, 403, 151, 254, 399, 432]),
    (38, 52, [ 60, 176, 368, 239,  12, 226,  86,  94,  39, 295,  70, 434, 378, 467]),
    (42, 71, [101,  97, 402, 317, 492, 152, 256, 301, 280, 286, 441, 365, 189, 444, 119])
]


class ComparisonCounter(object):
    count = 0

    def compare(self, x, y):
        self.count += 1
        return x - y


for mins, cxxs, nums in SETUP:
    cmpcounter = ComparisonCounter()
    nums.sort(key=functools.cmp_to_key(cmpcounter.compare))
    print("For %2d items: 'Minimum' %2d, Python %2d, C++ %2d" % (
            len(nums), mins, cmpcounter.count, cxxs))

sortcount.reb

REBOL []

setup: [
;;  Exact number of comparisons per https://oeis.org/A036604,
;;     Number of comparisions required by @HostileFork's C++ test
;;        Number of comparisons reuqired by Python
;;           List of numbers used by @HostileFork's C++ test
     0  0  0 [383]
     1  1  1 [386 277]
     3  4  4 [415 293 335]
     5  6  6 [386 492 149 421]
     7  8 11 [362  27 190  59 263]
    10  9 16 [426  40 426 172 236 211]
    13 14 18 [368  67 429 282  30 362 123]
    16 17 23 [ 67 135 429 302  22  58  69 167]
    19 20 29 [393 456  11  42 229 373 421 419 284]
    22 21 24 [ 37 198 324 315 370 413  26  91 480 456]
    26 27 31 [373 362 170 496 281 305 425  84 327 336   5]
    30 29 26 [346 229 313 357 124 395  82  45 314 367 434 364]
    34 33 47 [ 43 250  87 308 276 178 288  84 403 151 254 399 432]
    38 38 52 [ 60 176 368 239  12 226  86  94  39 295  70 434 378 467]
    42 40 71 [101  97 402 317 492 152 256 301 280 286 441 365 189 444 119]
]

foreach [mins pys cxxs nums] setup [
    count: 0
    sort/compare nums func [x y] [++ count y - x]
    print format [
        {For } -2 { items: }
        {'Minimum' } -2 {, }
        {Rebol } -2 {, }
        {Python } -2 {, }
        {C++ } -2
    ] reduce [
        length? nums  mins  count  pys  cxxs
    ]
]