The number of comparisons is of course about twice as large, because Bubble Sort always does exactly n(n-1)/2 comparisons while Can't Believe sort always does exactly n*n comparisons.
https://play.rust-lang.org/?version=stable&mode=debug&editio...
Why is there any difference? Does the entire difference come from the iteration where i = 1?
> Bubble Sort always does exactly n(n-1)/2 comparisons
Bubble sort can do less than this. When you're bubbling down into a sorted list, and you find a value lower than you are, you can assume that all values below that one are also lower than you are and terminate the inner loop early.
Sometimes it's more swaps, and sometimes it's less. The vague pattern looks like Can't Believe Sort does slightly fewer swaps on larger lists, but that could also have been noise.
Why do you expect them to have exactly the same number of swaps?
> Bubble sort can do less than this.
Oh sorry yeah, I implemented bubble sort without any sort of early return, for a more direct comparison.
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
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.
An insertion op inserts one element into a sorted list. A bubble op bubbles the maximum (or minimum) element to the end of an unsorted list.
You're correct that this is also a good match to insertion sort. The reason for the preprocessing step is so that bubbling will always work to perform insertions. In insertion sort, it isn't necessary to start with the maximal element.
As discussed, unlike insertion sort it begins by finding the max element and places it first.
Following that it follows normal insertion sort pattern with one change. Insertion sort normally sorts the new element "downward". This sort sorts the new element "upward" from the smallest item. It still uses the same inline temporary slot that insertion sort uses, it's just more notable now because it's inserting the new item "bottom-up".
Well, the reason that's more notable is that doing it upward requires you to use swaps instead of an assignment chain. Going downward, you can remember the value you're going to insert all the way down the chain. Going upward, you're always placing the value you remember and then remembering a new value, which is much worse.
Yes, one bubble op is linear time. A bubble sort is a sequence of bubble ops on the unsorted portion of the list (which shrinks by one for each bubble op).
Meanwhile an insertion sort is a sequence of insertion ops into the sorted portion of a list. So I agree with your analysis, except that the featured sort is a pessimized insertion sort, not a pessimized bubble sort.
> No, a bubble op bubbles one element into the correct position in a sorted list.
Again, that's an insertion op, not a bubble op. I suppose an insertion op can be thought of as equivalent to a bubble op on an element prepended to a sorted list, but it doesn't make sense to call it a bubble op in the context of bubble sort, since bubble sort doesn't do that.
> For our purposes, there is no difference, because we're bubbling into a perfectly sorted list, so once our initial element stops moving, nothing else can move.
I think this is where you're going wrong. In a bubble sort, a bubble op is never run on a sorted list + 1 element. Instead, it's run only on the unsorted portion of the list.
1. The first pass (I think you call it the preprocessing step) is special in that it finds the maximum number and puts it in the first slot. The rest of the algorithm revolves around this max value (or at least I find it helpful to think of it that way). This is also the only time where j going above i makes any difference. After this pass we could stop the j loop when i == j but that would obviously complicate the code.
2. Second pass will always swap items in first and second slots since the first item is bigger than second (if they are equal, nothing happens). As noted in 1., j will keep going past i but it won't do anything since i is now pointing to the largest value in the array and the swap condition will never be met.
3. On third and all subsequent passes the value that a[i] is pointing to will be slotted in its right place in the sorted list that's being formed at the beginning of the array. This might require multiple swaps as j goes up and larger values go into the ith slot. Last thing that happens before j reaches i (so when j == i - 1) is always that the max value gets swapped from i-1 to i. This is basically what the second pass from 2. did.
4. The max value from 1. conceptually serves almost as a sentinel of sorts since it always represents the end of the list we've sorted so far and when j gets to i, it prevents the rest of j loop from doing anything. That's why the code can be so clean, without having to do any index arithmetic or short circuiting or any other complications. It's clean but definitely not simple, since it takes a while to wrap one's head around what's actually happening.
Bubble sort only ever compares adjacent elements. It only ever swaps adjacent elements. This is what makes bubble sort optimal (within constant factors) for an external sort on a tape drive. This is why anything else isn't a bubble sort.
def pseudobubble(lst):
n = len(lst) # give a name to the list length
for i in range(n-1, 0, -1): # i will range from n-1 down to 1 inclusive
if lst[i] > lst[i-1]:
swap(lst, i, i-1) # high values bubble down
for i in range(1, n): # 1 to n-1 inclusive
for j in range(i, 0, -1): # i down to 1 inclusive
if lst[j] < lst[j-1]:
swap(lst, j, j-1) # low values bubble down
The code in the paper compares and swaps non-adjacent elements nearly every time. It is absolutely horrible for an external sort on a tape drive. It's just not a bubble sort, nor is it sort of like one in any key behavioral detail.
I can try to explain that. The algorithm really is doing a bubble sort, with some unnecessary extra work added. It also does a bit of necessary extra work.
Here is the useful work done by the algorithm:
1. First, preprocess the list so that the maximal element occurs first. (It's a 1-indexed list, so position 1 holds the highest element of the list.)
2. Now, we consider an invariant: the part of the list up to (and including) the maximal element is always sorted. Right now that consists of indices 1-1, and since that range contains only one value it's necessarily sorted. We will use a variable ("i") to remember where the maximal element is.
3. Now, the outer loop: we start at the index immediately after the maximal element, index i+1. Whatever value is in there, we bubble it to the left (this is the inner loop), in the manner of a standard bubble sort: we compare it to index i, and if it's lower (which is always, since i holds the maximal element), we swap. Then we compare index i to index i-1, and so on. Once we find an element that is smaller than the one we've been bubbling to the left, we stop, and our invariant is restored: the list up to the maximal element is still sorted. But the space covered by the invariant has increased by one slot. We increment i.
4. The loop continues until i points to the last slot in the list, at which point we're done. The invariant tells us the the list up to i is sorted, and since i points to the last value in the list, the whole list is sorted.
-----
The algorithm I've described sends i forward from the beginning to the end of the list and j backwards from i+1 to the beginning of the list. The algorithm in the paper does all the same work, but it also does more work, instead having j cross the entire list every time. (It also sends j forwards, like i, but this doesn't matter.) The only reason for this is to make the algorithm simpler to write down. This is why it's "unoptimized bubble sort". Note that, in the algorithm of the paper, once the maximum value has been swapped into i, the check A[i] < A[j] can never succeed, but we ignore that and keep advancing j instead of just terminating the j loop. This looks especially stupid because the maximal value will always occur before i (except when i = 1, which is the stage that, in my algorithm, is called "preprocessing").
In a bubble sort, if your cursor is at 5, and you want to move A[6] to index 3, you need to make 3 swaps and 3 comparisons. In the paper's sort, when your cursor is at 5 and you want to move A[6] to index 3, you need to make 3 swaps and n comparisons, where n is the length of the full list.