Алгоритм сортировки, в который невозможно поверить: он работает, хотя не должен

I Can't Believe It Can Sort

Стэнли П. Ю. Фунг опубликовал статью о простейшем алгоритме сортировки, который на первый взгляд не может работать: два вложенных цикла сравнивают и меняют местами элементы без какой-либо логики. Несмотря на абсурдность, алгоритм корректно сортирует массив за O(n²). В статье приведён псевдокод и реализация на Java, а также объяснение, почему это чудо всё-таки возможно.

Причина, по которой он так назван, в том, что если вы посмотрите на псевдокод, то не подумаете, что он действительно может сортировать, но он сортирует.
  1. Someone

    Статья об этом с доказательством того, как/почему это работает: https://arxiv.org/pdf/2110.01111, где сказано:

    «В этом алгоритме нет ничего хорошего. Он медленный — очевидно, что алгоритм работает за время Θ(n2), будь то худший, средний или лучший случай. Он без необходимости сравнивает все пары позиций дважды (но см. раздел 3). Похоже, за ним нет никакой интуиции, и его корректность не совсем очевидна. Вы точно не захотите использовать его как первый пример, чтобы познакомить студентов с алгоритмами сортировки. Он не является стабильным, плохо работает для внешней сортировки, не может сортировать входные данные, поступающие онлайн, и не получает выгоды от частично отсортированных входных данных. Его единственная привлекательность может быть в простоте, с точки зрения количества строк кода и «симметрии» двух циклов».

  2. petercooper

    На тему забавных маленьких алгоритмов сортировки меня всегда умиляла «сонная сортировка»:

    a=[5,3,1,4,2];b=[];a.map(n=>setTimeout(()=>b.push(n),n))

    Очевидно, никогда не используйте это в реальности, но мне было интересно подумать о поведении и подводных камнях этого алгоритма в разных языках.

  3. senfiaj

    Похоже на неоптимальную сортировку вставками.

    После первого запуска вложенного цикла A[1] будет иметь наибольшее значение.

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

    После k-го (k >= 2) запуска вложенного цикла, если вы обратите внимание, k-й элемент будет вставлен в первые k-1 отсортированных элементов. Когда j >= i, он больше ничего не может сделать, так как A[k] будет содержать наибольшее значение.

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

  4. fwlr

    Есть две причины, по которым он (интуитивно) не должен работать: одна в том, что внутренний цикл for также начинается с начала, не проверяя, где находится внешний цикл for, что означает, что вы получите `compare(a[0], a[2]) == true`, но также получите `compare(a[2], a[0]) == false`, так что, казалось бы, вы не сможете извлечь никакого полезного смысла из результата `compare`. Другая в том, что знак сравнения перевернут.

    Однако каким-то образом эти две причины, по которым он не должен работать, взаимодействуют так, что точно компенсируют друг друга, создавая работающую сортировку!

  5. edflsafoiewq

    Ранее (2021): https://news.ycombinator.com/item?id=28758106

Ещё за этот день

2026-11-16