I learned about this from Matt Parker’s Stand-Up Maths channel. It was originally conceived as a counterexample, a sorting algorithm that was obviously broken, but it does actually sort correctly. The algorithm:
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]
It has a few quirks (like j accessing elements outside of i’s range, and the A[i] < A[j] comparator being backward) that should break it, but they all work together to make the algorithm correctly (if inefficiently) sort the input.
paper describing the algorithm in more detail.
not exactly (if i understand it correctly). the first swap of a pair, where
i < j, basically does not matter, since the same pair will be revisited one more time later with switched values (i = 8, j = 9does not matter.i = 9, j = 8does) and that is when the actual sorting happens. that is why the condition isif a[i] < a[j] then swap, which may seem countreintuitive, but we are comparing the values in the reversed order compared to most of the sorting algorithms.the
i < jpart can be seen as the part that is handled in bubble sort by making the inner loop progressively smaller as the array is partially sorted (not the same elements, but the same amount of work, sort of). it is just ignored here, which is obviously bad for any kind of efficiency, but it allows for that super simple code.