What is this odd sorting algorithm?
Oct 4
Some answer originally had this sorting algorithm:
for i from 0 to n-1:
for j from 0 to n-1:
if A[j] > A[i]:
swap A[i] and A[j]
Note that both i and j go the full range and thus j can be both larger and smaller than i, so it can make pairs both correct and wrong order (and it actually does do both!). I thought that's a mistake (and the author later called it that) and that this would jumble the array, but it does appear to sort correctly. It's not obvious why, though. But the code simplicity (going full ranges, and no +1 as in bubble sort) makes it interesting.
Is it correct? If so, why does it work? And does it have a name?
Python implementation with testing:
from random import shuffle
for _ in range(3):
n = 20
A = list(range(n))
shuffle(A)
print('before:', A)
for i in range(n):
for j in range(n):
if A[j] > A[i]:
A[i], A[j] = A[j], A[i]
print('after: ', A, '\n')
Sample output (Try it online!):
before: [9, 14, 8, 12, 16, 19, 2, 1, 10, 11, 18, 4, 15, 3, 6, 17, 7, 0, 5, 13]
after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
before: [5, 1, 18, 10, 19, 14, 17, 7, 12, 16, 2, 0, 6, 8, 9, 11, 4, 3, 15, 13]
after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
before: [11, 15, 7, 14, 0, 2, 9, 4, 13, 17, 8, 10, 1, 12, 6, 16, 18, 3, 5, 19]
after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Edit: Someone pointed out a very nice brand new paper about this algorithm. Just to clarify: We're unrelated, it's a coincidence. As far as I can tell it was submitted to arXiv before that answer that sparked my question and published by arXiv after my question.
python
1 answer
Accepted answer · original discussion
Oct 4
To prove that it's correct, you have to find some sort of invariant. Something that's true during every pass of the loop.
Looking at it, after the very first pass of the inner loop, the largest element of the list will actually be in the first position.
Now in the second pass of the inner loop, i = 1, and the very first comparison is between i = 1 and j = 0. So, the largest element was in position 0, and after this comparison, it will be swapped to position 1.
In general, then it's not hard to see that after each step of the outer loop, the largest element will have moved one to the right. So after the full steps, we know at least the largest element will be in the correct position.
What about all the rest? Let's say the second-largest element sits at position i of the current loop. We know that the largest element sits at position i-1 as per the previous discussion. Counter j starts at 0. So now we're looking for the first A[j] such that it's A[j] > A[i]. Well, the A[i] is the second largest element, so the first time that happens is when j = i-1, at the first largest element. Thus, they're adjacent and get swapped, and are now in the "right" order. Now A[i] again points to the largest element, and hence for the rest of the inner loop no more swaps are performed.
So we can say: Once the outer loop index has moved past the location of the second largest element, the second and first largest elements will be in the right order. They will now slide up together, in every iteration of the outer loop, so we know that at the end of the algorithm both the first and second-largest elements will be in the right position.
What about the third-largest element? Well, we can use the same logic again: Once the outer loop counter i is at the position of the third-largest element, it'll be swapped such that it'll be just below the second largest element (if we have found that one already!) or otherwise just below the first largest element.
Ah. And here we now have our invariant: After k iterations of the outer loop, the k-length sequence of elements, ending at position k-1, will be in sorted order:
After the 1st iteration, the 1-length sequence, at position 0, will be in the correct order. That's trivial.
After the 2nd iteration, we know the largest element is at position 1, so obviously the sequence A[0], A[1] is in the correct order.
Now let's assume we're at step k, so all the elements up to position k-1 will be in order. Now i = k and we iterate over j. What this does is basically find the position at which the new element needs to be slotted into the existing sorted sequence so that it'll be properly sorted. Once that happens, the rest of the elements "bubble one up" until now the largest element sits at position i = k and no further swaps happen.
Thus finally at the end of step N, all the elements up to position N-1 are in the correct order, QED.
3 question comments
Use comments to ask for clarification. Post a solution as an answer.
Oct 6