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

[vak]

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

[dmm]

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

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

[vak]

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

[dmm]

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

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

[vak]

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

[dmm]

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