6 ms·

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 ro

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

copypasterepeat 2y ago
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.
deleted 2y ago
[deleted]
InsideOutSanta 2y ago
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. (Edit) I gave it a shot: https://jsfiddle.net/odwh6cL5/45/ https://jsfiddle.net/odwh6cL5/45/
- varunneal 2y ago
  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)
- WantonQuantum 2y ago
  Thank you for this!
- bunabhucan 2y ago
  Add bubble sort in parallel and race them against each other!
  - InsideOutSanta 2y ago
    Here you go: https://jsfiddle.net/790sfL21/30/ https://jsfiddle.net/790sfL21/30/ The difference between the two algorithms becomes even more apparent if you rerun the sort after the list is already sorted.
    - bunabhucan 2y ago
      "Slower than bubblesort" is the acheivement here.
- layer8 2y ago
  Here are two other visualizations: https://www.youtube.com/watch?v=8raee-rvBw0 https://www.youtube.com/watch?v=8raee-rvBw0 https://www.youtube.com/watch?v=bydMm4cJDeU https://www.youtube.com/watch?v=bydMm4cJDeU
  - Mithriil 2y ago
    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.
- Mithriil 2y ago
  This looks like a cool progress bar.
  - InsideOutSanta 2y ago
    That's a neat idea!
sigmoid10 2y ago
>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.
- cogman10 2y ago
  Yeah, feels a lot like a reverse selection sort.
thaumasiotes 2y ago
> 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 of using a temporary variable to hold the values we're swapping, we just use the space after the maximal element (which makes `swap(&a6, temp)` redundant - after the optimization, those are the same address). † It matters a little bit - a bubble sort is free to terminate the inner loop as soon as the value being bubbled has found its correct position. But in the paper's algorithm, we have to find the correct position first, which is done by scanning every index that contains a lower value until we eventually find the first one that doesn't. That work is optimized out of a bubble sort. However, since the paper's sort is committed to scanning the entire list in the inner loop anyway, the fact that the order of bubbling is wrong doesn't require any more extra scanning beyond what they've already committed to.
vrighter 2y ago
The way I understood it, it's more similar to insertion sort, but you insert from the top instead of from the bottom of the already-sorted part.

copypasterepeat 2y ago

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.

deleted 2y ago

[deleted]

InsideOutSanta 2y ago

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. (Edit) I gave it a shot: https://jsfiddle.net/odwh6cL5/45/ https://jsfiddle.net/odwh6cL5/45/

varunneal 2y ago
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)
WantonQuantum 2y ago
Thank you for this!
bunabhucan 2y ago
Add bubble sort in parallel and race them against each other!
- InsideOutSanta 2y ago
  Here you go: https://jsfiddle.net/790sfL21/30/ https://jsfiddle.net/790sfL21/30/ The difference between the two algorithms becomes even more apparent if you rerun the sort after the list is already sorted.
  - bunabhucan 2y ago
    "Slower than bubblesort" is the acheivement here.
layer8 2y ago
Here are two other visualizations: https://www.youtube.com/watch?v=8raee-rvBw0 https://www.youtube.com/watch?v=8raee-rvBw0 https://www.youtube.com/watch?v=bydMm4cJDeU https://www.youtube.com/watch?v=bydMm4cJDeU
- Mithriil 2y ago
  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.
Mithriil 2y ago
This looks like a cool progress bar.
- InsideOutSanta 2y ago
  That's a neat idea!

sigmoid10 2y ago

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

cogman10 2y ago
Yeah, feels a lot like a reverse selection sort.

thaumasiotes 2y ago

> 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 of using a temporary variable to hold the values we're swapping, we just use the space after the maximal element (which makes `swap(&a6, temp)` redundant - after the optimization, those are the same address). † It matters a little bit - a bubble sort is free to terminate the inner loop as soon as the value being bubbled has found its correct position. But in the paper's algorithm, we have to find the correct position first, which is done by scanning every index that contains a lower value until we eventually find the first one that doesn't. That work is optimized out of a bubble sort. However, since the paper's sort is committed to scanning the entire list in the inner loop anyway, the fact that the order of bubbling is wrong doesn't require any more extra scanning beyond what they've already committed to.

vrighter 2y ago

The way I understood it, it's more similar to insertion sort, but you insert from the top instead of from the bottom of the already-sorted part.