A weird sorting algorithm

[dmm]

This actually works:

for i = 1 to n do
  for j = 1 to n do
    if A[i] < A[j] then
      swap A[i] and A[j]

Comments

[dmm]

https://arxiv.org/abs/2110.01111

"Is this the simplest (and most surprising) sorting algorithm ever?", by Stanley Fung (U. of Leicester)

[dmm]

Via https://twitter.com/k_saifullaah/status/1445746638702534663

and https://twitter.com/PetarV_93/status/1445743289727008771

[vak]

Переизобрели пузырьковую сортировку?

[dmm]

Да нет, вроде, какая же она пузырьковая? Она совершенно не стремится "переставлять в правильном порядке", этот алгоритм не смотрит на то, как соотносятся i и j. Наоборот, он начинает с того, что засовывает самый большой элемент в самое неподходящее для него место.

Вообще, это совсем не любительская работа и, по моему, очень изящная...

[vak]

Ну как же. После первой итерации самый большой элемент оказывается в A[1]. После второй итерации следующий по величине элемент оказывается в A[2], и так далее.

[dmm]

Да нет же, она сортирует по возрастанию, а не по убыванию.

(Загляните в статью, там очень изящный инвариант в доказательстве.)

[vak]

Да, действительно.
Однако если изменить второй цикл на "for j = i+1 to n do", сортировка станет вдвое быстрее, но по убыванию.

[dmm]

(Это, скорее, некоторая прикольная версия insertion sort, что автор подробно и объясняет.)

[juan_gandhi]

На Архиве статья запощена. Не стал смотреть доказательств. Красивое.

[dmm]

Очень красивое, да. Я разобрал доказательство (проще всего оказалось подсмотреть в статье инвариант, а детали доказательства додумать самому).

(Линки в комментах, по причине моей лени, сочетающейся со странностями дримовского редактора.)