87
ICantBelieveItCanSort Sort (piefed.blahaj.zone)
submitted 2 months ago by to c/programmer_humor@programming.dev
10 comments fedilink hide all child comments
 

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 are viewing a single comment's thread
view the rest of the comments
[–] 3 points 2 months ago

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);
    }
  }
}
  • permalink
  • fedilink
  • source
    •