3 ms·

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 doin

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 2y ago
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.

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 2y ago

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.