3 ms·

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.

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.

ColinWright 2y ago
You would appear to be wrong, because A[1] ends up with the smallest element. Specifically, on each case when i=2 and higher, j will still start at 1, so A[1] will still get referenced.
- jmholla 2y ago
  On the first pass, A[1] ends up the largest element. On subsequent passes, it ends up with the smallest element in A[1:i].
bmacho 2y ago
> 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. (This comment was entirely rewritten.)
- aclindsa 2y ago
  I assumed your parent meant "smallest" when they said "largest", and just got the sort order mixed up when commenting.
  - jmholla 2y ago
    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. Edit: The original article on this has a visualization that can help: https://unnamed.website/posts/i-cant-believe-it-can-sort/ https://unnamed.website/posts/i-cant-believe-it-can-sort/
- tasty_freeze 2y ago
  Thanks, I stand corrected! I am once again surprised it works at all. :-)

ColinWright 2y ago

You would appear to be wrong, because A[1] ends up with the smallest element. Specifically, on each case when i=2 and higher, j will still start at 1, so A[1] will still get referenced.

jmholla 2y ago
On the first pass, A[1] ends up the largest element. On subsequent passes, it ends up with the smallest element in A[1:i].

bmacho 2y ago

> 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. (This comment was entirely rewritten.)

aclindsa 2y ago
I assumed your parent meant "smallest" when they said "largest", and just got the sort order mixed up when commenting.
- jmholla 2y ago
  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. Edit: The original article on this has a visualization that can help: https://unnamed.website/posts/i-cant-believe-it-can-sort/ https://unnamed.website/posts/i-cant-believe-it-can-sort/
tasty_freeze 2y ago
Thanks, I stand corrected! I am once again surprised it works at all. :-)