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.
You must log in or # to comment.
That is just a bubble sort, except the comparisons are done in different order than conventional bubble sort…
Indeed it is, Matt mentions in the video that it was originally conceived as a counterexample for students first learning about sorting algorithms, and I think in that instance it makes sense to take bubble sort and try to mangle it so the students have at least some frame of reference while debugging it. It just so happens that the mangling produced a different, weird but still valid kind of bubble sort, which I find charming.
It really does look more broken the more I look. I began to think that it would sort odd and even lists in opposite orders, since half the time it’s comparing pairs the opposite way around.
it would sort odd and even lists in opposite orders
not sure why you see different behaviour based on parity, but it does sort in descending order. that is why the inequality operator in
if A[i] < A[j] then swapis reversed.
Seems straightforward enough. For j values of 1 to i it will not do anything because the largest element in the array has already been moved to position i in some earlier iteration in the i loop. For j values greater than i it then proceeds to find the largest remaining element place in position i.
For the
j > icase I think you’re right, it sorts largest to smallest (or, backwards), but for thej < icase it grabs larger values from[]that it initially moved to the top of the array and slots them back in, effectively (if roundabout-ly) correcting the backwards sorting of thej > ipart of the algorithm. Sort of a “two wrongs that accidentally make a right” maneuver.Sort of a “two wrongs that accidentally make a right” maneuver.
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.
I would expect something worse than bubble sort. No idea whether it will even work:
void reverse(auto A, int start, int end) { for (int i = 0; i < (end - start) / 2; i = i + 1) { auto tmp = A[start + i]; A[start + i] = A[end - i]; A[end - i] = tmp; } } for (int j = 0; j < N; j = j + 1) { for (int i = 0; i < N; i = i + 1) { if (A[i] < A[i + 1]) { reverse(A, i, N); } } }
