|
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. |