[justinpombrio]

Yeah, 2410 vs. 2509 swaps not including the first iteration. You should try measuring these things yourself, I'm not sure if it's doing what you think it's doing.

[thaumasiotes]

Well, I sort of agree with you and sort of disagree.

    from random import randrange

    def list_swap(lst, i, j):
        temp = lst[i]
        lst[i] = lst[j]
        lst[j] = temp


    def icbicsort(lst):
        swap_count = 0
        n = len(lst)
        for i in range(n):
            for j in range(n):
                if lst[i] < lst[j]:
                    swap_count += 1
                    list_swap(lst, i, j)
        return swap_count

    def bubble(lst):
        swap_count = 0
        n = len(lst)
        # preprocess
        # this is intentionally identical to icbicsort with i = 0
        for j in range(n):
            if lst[0] < lst[j]:
                swap_count += 1
                list_swap(lst, 0, j)
        # go forward, bubbling backward
        for i in range(1, n):
            for j in range(i, 0, -1):
                if lst[j] < lst[j-1]:
                    swap_count += 1
                    list_swap(lst, j-1, j)
        return swap_count

    def cmp(n=100):
        alst = []
        blst = []
        for t in range(n):
            value = randrange(65536)
            alst.append(value)
            blst.append(value)
        icb_swaps = icbicsort(alst)
        bubble_swaps = bubble(blst)
        print(f"icb: {icb_swaps} swaps; bubble: {bubble_swaps} swaps")
    
    # just for completeness
    def bubble_classic(lst):
        n = len(lst)
        sorted = False
        while not sorted:
            sorted = True
            for i in range(n-1):
                if lst[i] > lst[i+1]:
                    sorted = False
                    list_swap(lst, i, i+1)
    return

26 calls to cmp() produced identical swap counts in 24 cases and slight discrepancies (of 2 and 3 swaps, both favoring icbsort) in two cases. (For statistical purposes, this was a manual inspection where I stopped after getting the second discrepancy.)

If you're regularly seeing discrepancies, something is weird. If you're seeing them occasionally, I still think something is weird, but I'm prepared to believe that it's a bug in the code.

I will note, in support of the paper's actual thesis, that I wrote icbicsort() correctly on the first try, and I had to work many bugs out of bubble(). Maybe it's still bugged.