14 ms·

Well, I teach Algorithms, I think there is an obvious intuition as to why this works and I use this algorithm to introduce sorting.

ColinWright 5y ago
Do you really use this algorithm? Look more closely, if compares every element against every other element, and the comparison appears to be in the wrong order. This is not the Bubble Sort[0] as defined in Wikipedia. For one thing, it always has n^2 comparisons, is not always comparing adjacent elements, and does not terminate early. [0] There are some who disagree and claim that it is.
- dhruvdh 5y ago
  Yes. I can read. It finds the largest number and places it at `i`. In the next iteration the largest number from 0 to `i` is placed at `i+1` Right up until `j` reaches `i`. Leaving a trail of orderliness. As the value of `i` increases we approach and eventually equal ascending order. What’s non-intuitive or what makes the comparison in the wrong order? It’s much easier to explain if we just stop `j` at `i` each time.
  - ColinWright 5y ago
    > Yes. I can read. I apologise. Multiple comments elsewhere have been made by people who initially thought it was a Bubble Sort, and every other course and tutorial I know of starts with the Bubble Sort. So I admit to being surprised that you use this to teach algorithms. Personally, I find the algorithm given here completely unobvious, but perhaps that's just because I derived the Bubble Sort for myself back in the mid 70s, then read about O(n.log n) algorithms, and was hooked. For me, this algorithm is very misleading, but if you find it a useful teaching tool then I've learned something, and I find it intriguing. I'd be interested to know if it's used in any other courses. Do you know of any? snip description > What’s non-intuitive or what makes the comparison in the wrong order? It works, so obviously the comparison is right. But compare it with a classical Bubble Sort: procedure bubbleSort( A : list of sortable items ) n := length(A) repeat swapped := false for i := 1 to n-1 inclusive do /* if these are out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap(A[i-1], A[i]) swapped := true end if end for until not swapped end procedure It's looking to see if A[i-1] > A[i], because then they are the wrong way round. Compare that with the code in this submission: if A[i] < A[j] then ... It's the other direction, which pulls me up short. And it's comparing every place with every other place, whereas Bubble Sort only ever compares adjacent items. Being as familiar as I am with sorting algorithms in general, this, to me, feels unintuitive. I guess my intuition doesn't match yours.
    - dhruvdh 5y ago
      I see now that people seem to be equating intuition with making steady, obvious progress. If you think about the point of all the adjacent comparisons in the inner loop for bubble sort is, it is finding the largest number and moving it to the last place in the array. It keeps doing that in a loop, the next time the second largest is found and at the second last place, etc. This algorithm doesn’t particularly do anything different, it just finds the largest and places it at `i` instead of the last place in the array. You’ll find that as it does it’s thing the array from 0 to `i` is always in ascending order. It’s very easy to teach this algorithm, the next variation that stops the inner loop at `i` instead of `n`, and the next variation that doesn’t do unnecessary swaps, which ends up being insertion sort I think? I would have to check.
      - ColinWright 5y ago
        > This algorithm ... finds the largest and places it at `i` instead of the last place in the array. This is immediately where my intuition for the correctness of this algorithm falls down. When `i` is 1 (in a 1-based array) this algorithm starts by putting the largest element in the 1st location. Then it proceeds by putting the largest element in the 2nd location, then the 3rd, then the 4th, and so on, so I can see that the largest element ends up in the last place. What is harder to see is that in all the swapping about, it's guaranteed that the smallest ends up in the 1st location. > * You’ll find that as it does it’s thing the array from 0 to `i` is always in ascending order.* This requires (a) noticing that it's the invariant you want, and (b) showing that it's true. It feels like a lot more work than proving Bubble Sort works, and to me, it's a lot less "obvious" (for want of a better term). But in particular, you refer to "making steady, obvious progress." It's not obvious to me that in the mid-phases we are making progress. The largest element continues trudging upwards, yes, but it's not at all clear to me that what it leaves behind is ordered, and not chaotic. I recognise that I'm not you, and I'm not in the same position as your students, but I still find this algorithm requiring a lot more work to understand than the Bubble Sort. Is there any particular reason you use this algorithm as your starting point for teaching sorting?
        5y ago
  - jonsen 5y ago
    Your original comment does not show that you are one of the few able to just read and understand a simple algorithm. Look around the many comments here where people misread this simple algorithm and readily jumps to premature conclusions. In that light I don't think you can say "there is an obvious intuition".
  - areyousure 5y ago
    > I use this algorithm to introduce sorting. Do you have any (publicly-available) course materials that mention this algorithm? The OP mentions they were "unable to find any references to it", and I've been collecting references I find in this comment: https://news.ycombinator.com/item?id=28760986#28762275 https://news.ycombinator.com/item?id=28760986#28762275 > What’s non-intuitive or what makes the comparison in the wrong order? In a sibling comment, 'ColinWright compares this algorithm to bubble sort, which has the comparison in the other direction. Another similar algorithm is this selection sort which differs by one character: for i = 1 to n do for j = i to n do if A[i] < A[j] then swap A[i] and A[j] This also sorts the array, but in the opposite order. It's true that seen in the correct light, both of these algorithms can be seen to work, but it definitely confuses people. For example, these three answers on Math Stack Exchange and Stack Overflow are incorrect about the sorting order: https://math.stackexchange.com/a/876452 https://math.stackexchange.com/a/876452 https://stackoverflow.com/a/61970459 https://stackoverflow.com/a/61970459 https://stackoverflow.com/a/57118286 https://stackoverflow.com/a/57118286
  - SamBam 5y ago
    > What’s non-intuitive Well, for me what's non-intuitive is that if we started with a fairly-well ordered array: [ 1, 2, 3, 5, 8, 4, 9 ] The very first thing the algorithm would do would be to swap 1 and 2, even though they are already in the right order. The next thing it would do would be to swap 2 and 3, making it even worse. And so on, all the way down the line. It takes six swaps to put 1 finally back to where it belongs, and the rest of the array is hopelessly out of order. It does work, yes, and you can eventually grok it, but I feel like you're not being honest to call this a completely intuitive algorithm to new CS students.
- iainmerrick 5y ago
  Who said it was bubble sort? It’s clearly not.
  - ColinWright 5y ago
    There are others in this discussion who are claiming that it is Bubble Sort. Some have recanted, others are sticking to their guns. I am in email conversation with someone who is claiming that it is just a more efficient version of the original Bubble Sort, and I'm trying to get the time to track down their references. So: I don't think it is Bubble Sort, I think it's clearly different, I have said so elsewhere, not everyone agrees.
cwoolfe 5y ago
Right. Isn't the intuition that the comparison and swap rule is applied to every possible combination? Put another way: How can you rearrange everything based on order and expect the net result to not be ordered at the end?
- kilovoltaire 5y ago
  Note that the comparison is backwards, so by that line of thinking it would sort in reverse (descending) order …but it doesn't
iainmerrick 5y ago
Hmm, come to think about it, it does have a lot going for it as an illustrative algorithm! - It’s really simple - It’s a bit counterintuitive, so makes a cute puzzle - It’s a good exercise for a first correctness proof - And it’s obviously a pretty pessimal algorithm, so students shouldn’t be tempted to use it in real code (hopefully...) Compared to bubble sort, which seems somewhat plausible, so people end up actually using it for real even though it’s a terrible algorithm.
ColinWright 5y ago
I've seen now from other comments that I'm not alone in finding this algorithm intuitive. Can you share with us your intuition as to why it works?

ColinWright 5y ago

Do you really use this algorithm? Look more closely, if compares every element against every other element, and the comparison appears to be in the wrong order. This is not the Bubble Sort[0] as defined in Wikipedia. For one thing, it always has n^2 comparisons, is not always comparing adjacent elements, and does not terminate early. [0] There are some who disagree and claim that it is.

dhruvdh 5y ago
Yes. I can read. It finds the largest number and places it at `i`. In the next iteration the largest number from 0 to `i` is placed at `i+1` Right up until `j` reaches `i`. Leaving a trail of orderliness. As the value of `i` increases we approach and eventually equal ascending order. What’s non-intuitive or what makes the comparison in the wrong order? It’s much easier to explain if we just stop `j` at `i` each time.
- ColinWright 5y ago
  > Yes. I can read. I apologise. Multiple comments elsewhere have been made by people who initially thought it was a Bubble Sort, and every other course and tutorial I know of starts with the Bubble Sort. So I admit to being surprised that you use this to teach algorithms. Personally, I find the algorithm given here completely unobvious, but perhaps that's just because I derived the Bubble Sort for myself back in the mid 70s, then read about O(n.log n) algorithms, and was hooked. For me, this algorithm is very misleading, but if you find it a useful teaching tool then I've learned something, and I find it intriguing. I'd be interested to know if it's used in any other courses. Do you know of any? snip description > What’s non-intuitive or what makes the comparison in the wrong order? It works, so obviously the comparison is right. But compare it with a classical Bubble Sort: procedure bubbleSort( A : list of sortable items ) n := length(A) repeat swapped := false for i := 1 to n-1 inclusive do /* if these are out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap(A[i-1], A[i]) swapped := true end if end for until not swapped end procedure It's looking to see if A[i-1] > A[i], because then they are the wrong way round. Compare that with the code in this submission: if A[i] < A[j] then ... It's the other direction, which pulls me up short. And it's comparing every place with every other place, whereas Bubble Sort only ever compares adjacent items. Being as familiar as I am with sorting algorithms in general, this, to me, feels unintuitive. I guess my intuition doesn't match yours.
  - dhruvdh 5y ago
    I see now that people seem to be equating intuition with making steady, obvious progress. If you think about the point of all the adjacent comparisons in the inner loop for bubble sort is, it is finding the largest number and moving it to the last place in the array. It keeps doing that in a loop, the next time the second largest is found and at the second last place, etc. This algorithm doesn’t particularly do anything different, it just finds the largest and places it at `i` instead of the last place in the array. You’ll find that as it does it’s thing the array from 0 to `i` is always in ascending order. It’s very easy to teach this algorithm, the next variation that stops the inner loop at `i` instead of `n`, and the next variation that doesn’t do unnecessary swaps, which ends up being insertion sort I think? I would have to check.
    - ColinWright 5y ago
      > This algorithm ... finds the largest and places it at `i` instead of the last place in the array. This is immediately where my intuition for the correctness of this algorithm falls down. When `i` is 1 (in a 1-based array) this algorithm starts by putting the largest element in the 1st location. Then it proceeds by putting the largest element in the 2nd location, then the 3rd, then the 4th, and so on, so I can see that the largest element ends up in the last place. What is harder to see is that in all the swapping about, it's guaranteed that the smallest ends up in the 1st location. > * You’ll find that as it does it’s thing the array from 0 to `i` is always in ascending order.* This requires (a) noticing that it's the invariant you want, and (b) showing that it's true. It feels like a lot more work than proving Bubble Sort works, and to me, it's a lot less "obvious" (for want of a better term). But in particular, you refer to "making steady, obvious progress." It's not obvious to me that in the mid-phases we are making progress. The largest element continues trudging upwards, yes, but it's not at all clear to me that what it leaves behind is ordered, and not chaotic. I recognise that I'm not you, and I'm not in the same position as your students, but I still find this algorithm requiring a lot more work to understand than the Bubble Sort. Is there any particular reason you use this algorithm as your starting point for teaching sorting?
      - 5y ago
- jonsen 5y ago
  Your original comment does not show that you are one of the few able to just read and understand a simple algorithm. Look around the many comments here where people misread this simple algorithm and readily jumps to premature conclusions. In that light I don't think you can say "there is an obvious intuition".
- areyousure 5y ago
  > I use this algorithm to introduce sorting. Do you have any (publicly-available) course materials that mention this algorithm? The OP mentions they were "unable to find any references to it", and I've been collecting references I find in this comment: https://news.ycombinator.com/item?id=28760986#28762275 https://news.ycombinator.com/item?id=28760986#28762275 > What’s non-intuitive or what makes the comparison in the wrong order? In a sibling comment, 'ColinWright compares this algorithm to bubble sort, which has the comparison in the other direction. Another similar algorithm is this selection sort which differs by one character: for i = 1 to n do for j = i to n do if A[i] < A[j] then swap A[i] and A[j] This also sorts the array, but in the opposite order. It's true that seen in the correct light, both of these algorithms can be seen to work, but it definitely confuses people. For example, these three answers on Math Stack Exchange and Stack Overflow are incorrect about the sorting order: https://math.stackexchange.com/a/876452 https://math.stackexchange.com/a/876452 https://stackoverflow.com/a/61970459 https://stackoverflow.com/a/61970459 https://stackoverflow.com/a/57118286 https://stackoverflow.com/a/57118286
- SamBam 5y ago
  > What’s non-intuitive Well, for me what's non-intuitive is that if we started with a fairly-well ordered array: [ 1, 2, 3, 5, 8, 4, 9 ] The very first thing the algorithm would do would be to swap 1 and 2, even though they are already in the right order. The next thing it would do would be to swap 2 and 3, making it even worse. And so on, all the way down the line. It takes six swaps to put 1 finally back to where it belongs, and the rest of the array is hopelessly out of order. It does work, yes, and you can eventually grok it, but I feel like you're not being honest to call this a completely intuitive algorithm to new CS students.
iainmerrick 5y ago
Who said it was bubble sort? It’s clearly not.
- ColinWright 5y ago
  There are others in this discussion who are claiming that it is Bubble Sort. Some have recanted, others are sticking to their guns. I am in email conversation with someone who is claiming that it is just a more efficient version of the original Bubble Sort, and I'm trying to get the time to track down their references. So: I don't think it is Bubble Sort, I think it's clearly different, I have said so elsewhere, not everyone agrees.

cwoolfe 5y ago

Right. Isn't the intuition that the comparison and swap rule is applied to every possible combination? Put another way: How can you rearrange everything based on order and expect the net result to not be ordered at the end?

kilovoltaire 5y ago
Note that the comparison is backwards, so by that line of thinking it would sort in reverse (descending) order …but it doesn't

iainmerrick 5y ago

Hmm, come to think about it, it does have a lot going for it as an illustrative algorithm! - It’s really simple - It’s a bit counterintuitive, so makes a cute puzzle - It’s a good exercise for a first correctness proof - And it’s obviously a pretty pessimal algorithm, so students shouldn’t be tempted to use it in real code (hopefully...) Compared to bubble sort, which seems somewhat plausible, so people end up actually using it for real even though it’s a terrible algorithm.

ColinWright 5y ago

I've seen now from other comments that I'm not alone in finding this algorithm intuitive. Can you share with us your intuition as to why it works?