이 코드가 정렬을 한다고? 믿기 힘든 정렬 알고리즘의 반전

I Can't Believe It Can Sort

Stanley P. Y. Fung의 논문에서 가져온 'I Can't Believe It Can Sort'는 이중 루프 안에서 A[i] < A[j]일 때마다 두 원소를 맞바꾸는 단순한 의사코드다. 얼핏 보면 정렬이 될 것 같지 않지만 실제로 배열을 정렬하며, 시간 복잡도는 O(n^2)로 퀵소트나 병합 정렬보다 훨씬 비효율적이다. Java 구현과 예제 실행 결과도 함께 소개한다.

의사코드를 보면 실제로 정렬할 수 있을 거라고 생각하지 않을 것이기 때문에 이런 이름이 붙었지만, 실제로는 정렬이 된다.
  1. Someone

    이것이 어떻게/왜 작동하는지에 대한 증명이 담긴 논문: https://arxiv.org/pdf/2110.01111, 논문에서는 이렇게 말합니다:

    “이 알고리즘에는 좋은 점이 하나도 없다. 느리다 – 이 알고리즘은 최악의 경우, 평균적인 경우, 최선의 경우 모두 Θ(n2) 시간에 실행된다. 모든 위치 쌍을 불필요하게 두 번씩 비교한다(단, 3절 참조). 그 뒤에 어떤 직관도 없는 것 같고, 정확성도 완전히 명백하지는 않다. 학생들에게 정렬 알고리즘을 소개하는 첫 번째 예제로 절대 쓰고 싶지 않을 것이다. 안정적이지 않고, 외부 정렬에 잘 작동하지 않으며, 온라인으로 도착하는 입력을 정렬할 수 없고, 부분적으로 정렬된 입력에서 이점을 얻지도 못한다. 유일한 매력은 코드 줄 수와 두 루프의 '대칭성' 측면에서의 단순함일 것이다.”

  2. petercooper

    재미있는 작은 정렬 알고리즘 이야기라면, 저는 항상 "sleep sort"에 감탄했습니다:

    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]로 가져온다는 점에서 특별하고, 연속된 루프들은 단지 배열의 시작부터 정렬된 처음 k-1개의 원소들에 A[k]를 삽입하는 것일 뿐입니다.

  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