It is not, it is actually closer to an insertion sort.
The interesting part is that it often comes up when the one writing the algorithm doesn't know what he is doing, and yet, it works. It may look like a BubbleSort because it is a common wrong implementation of BubbleSort.
Yeah, section 3.2 of the PDF, titled '"Improving" the algorithm' notes that they have "rediscovered" insertion sort by simply adjusting the loop indices.
(they also document a variant in 3.1 with similar indices tweaking which they describe as similar to an exchange sort)
I had to change the order of the rows and columns of a matrix to force the diagonal to be ordered. One possibility was to use the sort function on the diagonal, somehow get the permutation, and then apply the permutation to all the rows and columns. How had can it be?
There is a 50% chance of apply the permutation in the wrong direction, and other possible tricky details.
Since the worst case was N=20, I used bubble sort that is as quick and dirty, but it's also obvious and well known.
The really unintuitive bit is that the condition is the reverse of what you would expect, so I wouldn't call it "easy to get right".
Exchange sort is more intuitive and almost as simple, and if you don't mind something a little less intuitive but still very simple, just do insertion, it is often considered the best of the simple (N^2) sorting algorithms.
For me, the most intuitive and the less likely I would get wrong would be selection. It is actually the one I came up with naturally before I even knew about sorting algorithms, it is a couple of lines longer than the others though, and often considered worse than insertion.
This isn't surprising to me in the least that it works.
In the first pass (i=1), A[1] will end up with the largest value and a later pass cannot displace it.
In the second pass (i=2), A[2] will end up with the 2nd largest value (which might be the same as the largest value, if it appeared more than once in the list). And so on.
> In the first pass (i=1), A[1] will end up with the largest value and a later pass cannot displace it.
Nah, it will get displaced later. Notice that in the inner loop j goes from 1, and not from i. After i=1 A[1] will be the largest element, but after the next big step, after i=2, A[2] will be the largest element. (And after i=n, A[n] will be the largest element, as expected.)
> In the second pass (i=2), A[2] will end up with the 2nd largest value
The algorithm sorts the array ascending, and not descending. There is an example run linked in a grandkid comment, by jmholla.
That's actually not correct at all either. After the first pass makes the largest element the first element, every pass after that is a single iteration of (reverse) bubble sorting the beginning of the array, increasing the array that is sorted. So, the second pass doesn't end up with the largest or smallest of the list, just the smallest of the selected prefix.
Once the iterator reaches beyond the length of the tested prefix, we know every element after it will be smaller because we bubbled the largest element to the iteration point which means we won't do any checks there after. In fact, excepting the first pass, this inner loop can break whenever it sees it is comparing against itself.
Feels oddly familiar; I'm pretty sure this was the optimal solution to a leetcode problem (with specific constraints) that I saw during interview practice. Coming up with this on the fly during an interview would have been extra impressive.
Question on paper writing... There is only one author listed, but the wording keeps using "we" as in "we show that..." Is it considered poor practice to use "I" in a one-person paper? Or is "we" including the reader in the exposition?
The “royal we” is common for single author academic work. I’m honestly unsure why. StackExchange seems to think it refers to both author and reader together. I think it conveys a sort of distance from the author, giving the writing less of a personal and more general tone.
It's assumed you at some point talked to someone in the lab, or your advisor, or your advisee, or literally anyone about the paper. If you didn't that's probably problematic. So "we" gives non-formal credit to your community.
I have never heard that as an explanation. That kind of credit is often expressed in foot/end notes, at least in the field I worked in. It is implied that the authors speak for themselves.
Well IMO if you're giving some trivial level of credit someone else, you should use 'we', since you're both 'talking. If you reference them by name in the paper somewhere, I feel even stronger about my stance.
I did search for "trivial sorting network", but the only networks that were called trivial were the ones for exactly two elements, while this algorithm sorts an arbitrary number of elements.
Could you link to what you're talking about? And what's its big-O runtime?
This is a sort I use all the time. Especially in coding challenges (AoC) because I'm usually lazy. It's nice to see it formally evaluated, it feels very intuitive to me.
Would you be willing ... without looking at this article ... to provide exactly the code you "use all the time"?
I'd like to compare what you write with the code in the article, because code that I write as a quick and dirty sort is definitely not this.
In particular, this seems to take items that are already the right way round, and swaps them. I definitely don't do that. To be specific, I just knocked this out:
#!/usr/bin/python
a = [ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 ]
N = len(a)
for i in range(0,N-2):
for j in range(i+1,N-1):
if a[i]>a[j]:
a[i],a[j] = a[j],a[i]
print a
Specifically, note that I ask if a[i] is bigger than a[j] and if so then I swap them. The code in the article appears to do exactly the wrong thing, and I'd be surprised if your "go to" code does it the same way as the code in the article.
instructions = []
updates = []
with open("input.txt") as file:
for line in file:
line = line.rstrip()
if line == "":
break
x, y = line.split('|')
instructions.append((int(x), int(y)))
for line in file:
line = line.rstrip()
pages = [int(i) for i in line.split(',')]
updates.append(pages)
def is_valid_update(update, instructions):
pos = {num: idx for idx, num in enumerate(update)}
for x, y in instructions:
if x in pos and y in pos and pos[x] > pos[y]:
return False
return True
valid_updates = [upd for upd in updates if is_valid_update(upd, instructions)]
accum_valid = sum(upd[len(upd) // 2] for upd in valid_updates)
print("Sum from valid updates:", accum_valid)
def domain_sort(update, instructions):
n = len(update)
for i in range(n):
for j in range(n):
if (update[j], update[i]) in instructions:
update[i], update[j] = update[j], update[i]
return update
invalid_updates = [upd for upd in updates if not is_valid_update(upd, instructions)]
sorted_updates = [domain_sort(upd.copy(), instructions) for upd in invalid_updates]
print("Sorted invalid updates:")
for upd in sorted_updates:
print(upd)
accum_sorted = sum(upd[len(upd) // 2] for upd in sorted_updates)
print("Sum from sorted invalid updates:", accum_sorted)
I would have a hard time understanding why this finishes with the "updates" in the order expected instead of the opposite order, and I'm intrigued. In the paper it just seems to counter-intuitive to me that if the comparison is that way round then the items get swapped ... if I found this in code I was auditing then I'd spent a long time trying to work out what was going on.
Yes, not something I would write in production code. But very easy for me to think about in a stream of consciousness. Usually I complete the above challenges in about 5-10mins.
This isn't even worthy of a blog post let alone a published research article, the publisher should be embarrassed.
This isn't an innovation. It's just un-optimized bubble sort. Back in college when I was learning bubble sort, I implemented this exact sort as a type of "MVP". And then I added the other flags and stuff they reference to try to polish the turd.
I mean I'm glad someone proved it works, but I thought they proved this works like 40 years ago.
On any bubble sort, optimised or not, no swaps are made on an array that's already sorted.
The routine in the article does.
So no, it's not a bubble sort, unoptimised or otherwise.
If you think it is a bubble sort then I'd be interested in seeing your implementation of a bubble sort, and an explanation as to why they are effectively the same.
Is this a joke paper? This is unoptimized bubble sort. This is the first sort I wrote when I was 13. This is literally the most obvious sort that exists.
Lots of people in this thread saying that it's just an unoptimised Bubble Sort.
No, it really isn't.
In bubble sort you see if two things are the wrong way round and it they are then you swap them. This does that (sort of) the "wrong way round".
In Bubble Sort your indices are always i<j ... here they aren't.
In Bubble Sort you only ever compare adjacent items. Here you don't.
This really, really isn't Bubble Sort, unoptimised or other.
Also, with Bubble Sort it's really easy to prove that it works. If you think this is "just unoptimised Bubble Sort" then I'd be interested to see your proof that this algorithm works.
So my feeling is that when people are dismissive of this, either they've not understood this at all, or they've understood it at a really, really deep level that I haven't. In that latter case I'd really appreciate a better explanation for what you think is going on, and why you think this is "just an unoptimised Bubble Sort".
I agree. At first I thought it was doing something very simple but I am not so sure anymore. When you check the condition for the swap, you realize it almost works counterproductively while i<j because it keeps pushing smaller numbers in the wrong direction, but then it starts "fixing" those mistakes when i>j. I don't find this intuitive at all.
The problem is that you can look at this and, after a few seconds, think you've formed an intuition on how it must work, but your intuition is wrong. It seems like the only way to really show how weird this is would be by creating an animation that shows how it shuffles entries around.
very beautiful simple animation. Good visualization of the proof of the algo; namely, that at each step i of the outer loop the first i elements are sorted (this is easy to show via induction)
The visualization helped me realize something: The index doesn't change after the swap, so you always end up with the biggest number "in hand" after a full deeper level iteration loop.
>In Bubble Sort you only ever compare adjacent items. Here you don't.
This is the first thing I noticed and it pretty much says it all. It is not bubble sort because there are no bubbles bubbling to the top. Instead it compares every possible element pair combination.
> In that latter case I'd really appreciate a better explanation for what you think is going on, and why you think this is "just an unoptimised Bubble Sort".
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.
-----
If you're interested in why the j loop is the same thing as a bubble sort, here's an expansion on the example above:
We're in the process of bubble sorting [1 4 8 11 24 5], looking at the 5. Because 5 is more than 4 but less than 8, we want it to ultimately end up at index 3. Everything else will shift up by one index to accommodate this.
In a bubble sort, we swap the 5 down into index 5, then we swap the 5 down into index 4, and then we swap it down into index 3.
swap(&a6, &a5);
swap(&a5, &a4);
swap(&a4, &a3);
In the paper's sort, we do exactly the same thing from the other direction:
int* temp;
*temp = a6; /* we want to put this into its correct position */
swap(&a3, temp); /* done, but we need to remember what was in a3 so we can swap it up to a4 */
swap(&a4, temp); /* done, but now we need to remember what was in a4 so we can swap it up to a5 */
swap(&a5, temp); /* take a guess... */
swap(&a6, temp);
but there's a slight optimization where instead ...
The number of swaps is nearly the same between Bubble Sort and Can't Believe Sort. For a random list with 100 elements, it's 2505 swaps vs. 2513 swaps.
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.
> The number of swaps is nearly the same between Bubble Sort and Can't Believe Sort. For a random list with 100 elements, it's 2505 swaps vs. 2513 swaps.
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.
> Why is there any difference? Does the entire difference come from the iteration where i = 1?
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.
I expect them to have exactly the same number of swaps in every iteration of the loop past the first one, because they are doing exactly the same thing. It's not just the same number of swaps. It's essentially the same set of swaps, in a different order. In the iteration where i = 1, the number of swaps may differ. Was I wrong about that?
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.
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.
No, a bubble op bubbles one element into the correct position in a sorted list. If it was restricted to bubbling the maximum or minimum to the end of the list, the full sort would use one bubble, it would complete in linear time, and the list wouldn't be sorted afterwards.
You're correct that this is also a good match to insertion sort, but only conceptually.
(Note that one classic bubblesort pass moves several elements when the data is unsorted - when an element has bubbled as far as it can go, the bubblesort pass picks up the element that blocked it and carries that one further, and this process repeats until the end of the data is reached. 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.)
The bigger difference between an insertion op and a bubble op is in the number of assignments.
This is the chain of operations you get while bubbling:
swap(a5, a6)
swap(a4, a5)
swap(a3, a4)
This is the chain of operations you get while inserting:
temp = a6
a6 = a5
a5 = a4
a4 = a3
a3 = temp
Inserting never does any swaps. But each swap is three assignments, so the bubble in this case does nine assignments to the insertion's five. (And in general, if you need to sink a value n places into the data, bubbling it there will take 3n assignments, and inserting it there will take n+2.) That is the advantage of knowing where you're going before you get there.
There are two variations of insertion sort. You are comapring to the swapless insertion sort, the other poster is comparing to the swap basses insertion sort. This is the swap based insertion sort with a small variation.
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".
> 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 overwriting a value that you must immediately remember, which is worse.
> If it was restricted to bubbling the maximum or minimum to the end of the list, the full sort would use one bubble, it would complete in linear time, and the list wouldn't be sorted afterwards.
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.
Yeah, this makes sense to me. I started developing some of these similar intuitions while watching a visualization another commenter posted.
Here are some things I realized:
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.
This is a strange argument to me, because the single most critical aspect of a bubble sort is the locality.
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.
Here's an algorithm (in Python) that is exactly equivalent to the one in the paper:
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 first pass of this algorithm (bubbling high values down, one time only) may do different things than the first pass of the paper's algorithm, but that's not relevant.
All comparisons and swaps in the code you quoted are made between adjacent elements. It's local in a way that behaves very nicely for an external sort on a tape drive.
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.
This immediately made me wonder if there's some grand unified sorting algorithm, from which all other sorting algorithms can be derived. Could we somehow turn this thing into a quicksort, for example?
Each iteration of the outter loop restuls in the smallest element moving into `A[i]`. And then the first `i` iterations of the inner loop are just wasting time.
It just might be the simplest sorting algorithm ever. But it's still just an unoptimized insertion sorter, and it's not novel. One would often come across this in computer books from the 80s teaching basic programming concepts and techniques in, well, BASIC.
Nothing to do with the original article. This was my attempt at a joke. A totally failed attempt, for which I will have to endure shame and karma hits as it is too late to hide my stupid comment.
There is nothing good about this algorithm. It is slow – the algorithm
obviously runs in Θ(n2) time, whether worst-case, average-case or best-case.
It unnecessarily compares all pairs of positions, twice (but see Section 3).
There seems to be no intuition behind it, and its correctness is not entirely
obvious. You certainly do not want to use it as a first example to introduce
students to sorting algorithms. It is not stable, does not work well for
external sorting, cannot sort inputs arriving online, and does not benefit
from partially sorted inputs. Its only appeal may be its simplicity, in terms
of lines of code and the “symmetry” of the two loops.
I used to teach this to beginners all the time. I called it "exchange sort", though I'm not sure where I ever got that name from.
Beginners to sorting are often still somewhat struggling with for loops (especially the three-part C kind), struggling with indexing an array, struggling with swaps. It's overwhelming.
This is kind-of like pseudocode for a simple sort -- it has the same rough outline, but no tricky bits. It allows them to get their brains around the basic algorithm, and only after that you trace through an execution on the board to show them that it wastes a lot of time moving things around.
Then you can show them insertion sort as an optimization, and from that move on to fancier ones.
Can you give a reference to your teaching materials? The way this sort works is bizarre enough that I'm curious what you said about it. (Also to verify that this is actually the algorithm you taught, given how many other people thought it was something else.)
This is an awesome tool. I noticed a really fun bug here where if you start a new faster sort before a slower sort finishes the slower sort keeps going and you end up with a the two sorts running at the same time, I think against different sets of values. Don't know if I'd bother fixing it because the output is neat
129 comments
[ 3.3 ms ] story [ 172 ms ] thread(That's what ColinWright did at https://news.ycombinator.com/item?id=43162234 for example.)
Is this the simplest (and most surprising) sorting algorithm? - https://news.ycombinator.com/item?id=28758106 - Oct 2021 (318 comments)
For easier exposition in the proof later on, the array is 1-based, so the elements are A[1]...A[n].
And, if so: they're writing Arxiv papers on BubbleSort now?
The interesting part is that it often comes up when the one writing the algorithm doesn't know what he is doing, and yet, it works. It may look like a BubbleSort because it is a common wrong implementation of BubbleSort.
EDIT: insertion, not selection
(they also document a variant in 3.1 with similar indices tweaking which they describe as similar to an exchange sort)
I actually think it's pretty cool, it happens occasionally that I just need a quick and dirty sort and this is easier to get right.
There is a 50% chance of apply the permutation in the wrong direction, and other possible tricky details.
Since the worst case was N=20, I used bubble sort that is as quick and dirty, but it's also obvious and well known.
Sometimes I'm writing my own language, trying to figure something else out and don't feel like being sidetracked.
Sometimes predictable performance is more important than optimal.
Let's just say there are plenty of reasons why someone might want to do that.
Exchange sort is more intuitive and almost as simple, and if you don't mind something a little less intuitive but still very simple, just do insertion, it is often considered the best of the simple (N^2) sorting algorithms.
For me, the most intuitive and the less likely I would get wrong would be selection. It is actually the one I came up with naturally before I even knew about sorting algorithms, it is a couple of lines longer than the others though, and often considered worse than insertion.
In the first pass (i=1), A[1] will end up with the largest value and a later pass cannot displace it.
In the second pass (i=2), A[2] will end up with the 2nd largest value (which might be the same as the largest value, if it appeared more than once in the list). And so on.
Specifically, on each case when i=2 and higher, j will still start at 1, so A[1] will still get referenced.
Nah, it will get displaced later. Notice that in the inner loop j goes from 1, and not from i. After i=1 A[1] will be the largest element, but after the next big step, after i=2, A[2] will be the largest element. (And after i=n, A[n] will be the largest element, as expected.)
> In the second pass (i=2), A[2] will end up with the 2nd largest value
The algorithm sorts the array ascending, and not descending. There is an example run linked in a grandkid comment, by jmholla.
(This comment was entirely rewritten.)
Once the iterator reaches beyond the length of the tested prefix, we know every element after it will be smaller because we bubbled the largest element to the iteration point which means we won't do any checks there after. In fact, excepting the first pass, this inner loop can break whenever it sees it is comparing against itself.
Edit: The original article on this has a visualization that can help: https://unnamed.website/posts/i-cant-believe-it-can-sort/
https://hsm.stackexchange.com/questions/2002/how-did-royal-w...
Good reminder that Arxiv is not peer-reviewed :/
Could you link to what you're talking about? And what's its big-O runtime?
And now it's constant time!
Would you be willing ... without looking at this article ... to provide exactly the code you "use all the time"?
I'd like to compare what you write with the code in the article, because code that I write as a quick and dirty sort is definitely not this.
In particular, this seems to take items that are already the right way round, and swaps them. I definitely don't do that. To be specific, I just knocked this out:
Specifically, note that I ask if a[i] is bigger than a[j] and if so then I swap them. The code in the article appears to do exactly the wrong thing, and I'd be surprised if your "go to" code does it the same way as the code in the article.Cheers!
I would have a hard time understanding why this finishes with the "updates" in the order expected instead of the opposite order, and I'm intrigued. In the paper it just seems to counter-intuitive to me that if the comparison is that way round then the items get swapped ... if I found this in code I was auditing then I'd spent a long time trying to work out what was going on.
Thank you.
This isn't an innovation. It's just un-optimized bubble sort. Back in college when I was learning bubble sort, I implemented this exact sort as a type of "MVP". And then I added the other flags and stuff they reference to try to polish the turd.
I mean I'm glad someone proved it works, but I thought they proved this works like 40 years ago.
The routine in the article does.
So no, it's not a bubble sort, unoptimised or otherwise.
If you think it is a bubble sort then I'd be interested in seeing your implementation of a bubble sort, and an explanation as to why they are effectively the same.
Moreover the comparison is the opposite of what you would normally do: if A[i] < A[j] then swap(A[i], A[j])
I can’t believe that I can prove that it can sort - https://news.ycombinator.com/item?id=31975507 - Jul 2022 (115 comments)
Here's some other sorting algorithms proven with SPARK, with much more straightforward proofs: https://github.com/AdaCore/spark2014/blob/master/testsuite/g...
It's not a bubble sort. The article explains.
No, it really isn't.
In bubble sort you see if two things are the wrong way round and it they are then you swap them. This does that (sort of) the "wrong way round".
In Bubble Sort your indices are always i<j ... here they aren't.
In Bubble Sort you only ever compare adjacent items. Here you don't.
This really, really isn't Bubble Sort, unoptimised or other.
Also, with Bubble Sort it's really easy to prove that it works. If you think this is "just unoptimised Bubble Sort" then I'd be interested to see your proof that this algorithm works.
So my feeling is that when people are dismissive of this, either they've not understood this at all, or they've understood it at a really, really deep level that I haven't. In that latter case I'd really appreciate a better explanation for what you think is going on, and why you think this is "just an unoptimised Bubble Sort".
(Edit) I gave it a shot: https://jsfiddle.net/odwh6cL5/45/
The difference between the two algorithms becomes even more apparent if you rerun the sort after the list is already sorted.
https://www.youtube.com/watch?v=8raee-rvBw0
https://www.youtube.com/watch?v=bydMm4cJDeU
This is the first thing I noticed and it pretty much says it all. It is not bubble sort because there are no bubbles bubbling to the top. Instead it compares every possible element pair combination.
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.
-----
If you're interested in why the j loop is the same thing as a bubble sort, here's an expansion on the example above:
We're in the process of bubble sorting [1 4 8 11 24 5], looking at the 5. Because 5 is more than 4 but less than 8, we want it to ultimately end up at index 3. Everything else will shift up by one index to accommodate this.
In a bubble sort, we swap the 5 down into index 5, then we swap the 5 down into index 4, and then we swap it down into index 3.
In the paper's sort, we do exactly the same thing from the other direction: but there's a slight optimization where instead ...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.
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, but only conceptually.
(Note that one classic bubblesort pass moves several elements when the data is unsorted - when an element has bubbled as far as it can go, the bubblesort pass picks up the element that blocked it and carries that one further, and this process repeats until the end of the data is reached. 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.)
The bigger difference between an insertion op and a bubble op is in the number of assignments.
This is the chain of operations you get while bubbling:
This is the chain of operations you get while inserting: Inserting never does any swaps. But each swap is three assignments, so the bubble in this case does nine assignments to the insertion's five. (And in general, if you need to sink a value n places into the data, bubbling it there will take 3n assignments, and inserting it there will take n+2.) That is the advantage of knowing where you're going before you get there.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 overwriting a value that you must immediately remember, which is 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.
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.
https://en.m.wikipedia.org/wiki/Sorting_network
Each iteration of the outter loop restuls in the smallest element moving into `A[i]`. And then the first `i` iterations of the inner loop are just wasting time.
In the first iteration of the outer loop, i=1, and in that case the inner loop moves the largest element into A[1].
So I don't think you can be correct.
There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.
Beginners to sorting are often still somewhat struggling with for loops (especially the three-part C kind), struggling with indexing an array, struggling with swaps. It's overwhelming.
This is kind-of like pseudocode for a simple sort -- it has the same rough outline, but no tricky bits. It allows them to get their brains around the basic algorithm, and only after that you trace through an execution on the board to show them that it wastes a lot of time moving things around.
Then you can show them insertion sort as an optimization, and from that move on to fancier ones.
I made this tool to vi's sorting algos long time ago.