3 ms·

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 i

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?
- dhruvdh 5y ago
  It’s a lot more work to massage bubble sort into the other sorting algorithms they need to learn without scraping the code and starting from scratch.
- dhruvdh 5y ago
  The algorithm is essentially just inserting the i + 1 th element into the sorted subarray from 0 to i, and it inserts in the correct place. I’ll be teaching this next week or the one after, I’ll try to record a video and share if I remember. It’s harder to explain with just words.
  - ColinWright 5y ago
    I'd be fascinated to see this ... if you can do that I'd be grateful ... thank you. (Copying from your sibling comment) > It’s a lot more work to massage bubble sort into the other sorting algorithms they need to learn without scraping the code and starting from scratch. An interesting observation. When I teach equivalent things I tend to present them separately and individually, so the students recognise that they are different in important ways, and then cross-connect them with transformations or other bridging techniques. Then they can see that they are different, but related. I'll think about your approach next time I do something like this. Meanwhile, if you would be willing to share a video of teaching this topic I'd be pleased to see it ... contact details are in my profile if you'd prefer direct contact, although I'm sure others would also be interested.
  - dtjc 5y ago
    I'd like to watch that video as well.

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?

dhruvdh 5y ago
It’s a lot more work to massage bubble sort into the other sorting algorithms they need to learn without scraping the code and starting from scratch.
dhruvdh 5y ago
The algorithm is essentially just inserting the i + 1 th element into the sorted subarray from 0 to i, and it inserts in the correct place. I’ll be teaching this next week or the one after, I’ll try to record a video and share if I remember. It’s harder to explain with just words.
- ColinWright 5y ago
  I'd be fascinated to see this ... if you can do that I'd be grateful ... thank you. (Copying from your sibling comment) > It’s a lot more work to massage bubble sort into the other sorting algorithms they need to learn without scraping the code and starting from scratch. An interesting observation. When I teach equivalent things I tend to present them separately and individually, so the students recognise that they are different in important ways, and then cross-connect them with transformations or other bridging techniques. Then they can see that they are different, but related. I'll think about your approach next time I do something like this. Meanwhile, if you would be willing to share a video of teaching this topic I'd be pleased to see it ... contact details are in my profile if you'd prefer direct contact, although I'm sure others would also be interested.
- dtjc 5y ago
  I'd like to watch that video as well.