생활코딩에서 신기한 정렬 알고리즘을 접했습니다.
이게 왜 되지? 싶지만 놀랍게도 오름차순으로 잘 정렬됩니다!!
논문 링크도 있길래 읽어 보았습니다.
아래는 위 논문을 참고한 알고리즘 정당성 증명입니다.
초기 배열에 같은 수가 없다고 가정하고 작성했지만, 있어도 큰 차이는 없습니다.
정당성 증명
위 알고리즘을 그대로 구현하고, 과정을 확인하기 위해 swap 직후마다 배열 전체를 출력하는 코드를 추가했습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <bits/stdc++.h>
using namespace std;
int arr[1000];
void print(int* a, int n) {
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
cout << '\n';
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
cout << "i,j -> [array after swap]\n";
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (arr[i] < arr[j]) {
swap(arr[i], arr[j]);
cout << i << "," << j << " -> "; print(arr, n);
}
return 0;
}
|
cs |
아래는 위 코드의 실행결과입니다.
위 실행결과를 잘 관찰해 보면 다음 사실을 알 수 있습니다.
배열을 $A$, 배열의 $x$번째 원소를 $A[x]$, $x$번째 원소부터 $y$번째 원소까지는 $A[x:y]$라고 하겠습니다(인덱스는 1부터 시작합니다)
- $i = x$인 바깥 반복문이 종료되면 $A[x]$에는 배열 전체의 최댓값이 저장되어 있다.
- P(x) : $i = x$인 바깥 반복문이 종료되면 $A[1:x]$는 오름차순으로 정렬되어 있다.
이 알고리즘에서는 $i = x$인 반복문에서 모든 배열을 보며 $A[x]$보다 큰 값을 찾으면 $A[x]$와 swap하므로 첫 번째 명제는 쉽게 증명됩니다.
P(x)가 항상 참이라면 P(n) 또한 참이고, 이는 마지막 바깥 반복문이 종료되면 배열 전체가 오름차순으로 정렬되어 있다는 의미이므로 알고리즘의 정당성 또한 증명됩니다. P(x)는 귀납법을 이용해 증명할 수 있습니다.
1. P(1)은 참이다: $A[1:1]$의 원소는 하나이므로 P(1)은 항상 참입니다.
2. P(x)가 참이라면 P(x+1)이 항상 참이다:
$A[1:x]$에서 $A[x+1]$보다 큰 원소 중 가장 작은 원소의 인덱스를 $k$라고 하겠습니다. $A[1:x]$는 오름차순으로 정렬되어 있기 때문에 $A[1:k-1]$의 모든 원소는 $A[x+1]$보다 작고, $A[k:x]$의 모든 원소는 $A[x+1]$보다 큽니다. 해당 알고리즘에서는 $A[i] < A[j]$일 때 swap하므로, $i = x$인 반복문에서 $1 \leq j < k$인 동안에는 swap이 일어나지 않고 $k \leq j \leq x$인 동안에는 항상 swap이 일어납니다. 즉, $i = x$인 반복문이 끝나면 $A[1:k-1]$과 $A[k:x]$ 사이에 $A[x+1]$을 끼워넣은 형태가 되므로 $k$의 정의에 따라 $A[1:x+1]$은 정렬됩니다. $j \leq x + 1$인 경우를 모두 수행하면 $A[x+1]$에는 배열의 최댓값이 들어가게 되고, 따라서 $x + 1 < j$인 동안에는 swap이 일어나지 않습니다. 따라서 $i = x$인 바깥 반복문이 끝날 동안 $A[1:x + 1]$은 정렬된 상태로 유지되므로 P(x)가 참이라면 P(x + 1) 또한 항상 성립합니다.
즉, 이 알고리즘의 동작 과정은
1. i = 1인 반복문에서 배열의 최댓값을 $A[1]$으로 가져온다.
2. 나머지 반복문에서 i번째 원소를 적당한 위치에 삽입한다.
로 정리할 수 있습니다. 코드는 선택 정렬과 비슷하지만, 동작 과정은 삽입 정렬과 흡사합니다.
개선
알고리즘의 동작 방식을 자세히 살펴보면 두 가지 의문점이 생깁니다.
1. 오름차순으로 정렬하는데 굳이 최댓값을 첫 번째 원소로 가져와야 할까?
-> 굳이 그럴 필요가 없습니다!
2. swap이 발생하지 않는 $i \leq j$인 구간을 굳이 비교해보아야 할까?
-> 굳이 안 해봐도 됩니다! 물론 1. 에 의해 최댓값을 가져오지 않았다면 이 구간에서도 swap이 발생할 수 있지만, P(x)는 $A[x]$가 배열의 최댓값이 아니더라도 문제없이 성립하기 때문에 굳이 이 구간에서 swap을 하지 않아도 올바르게 정렬할 수 있습니다.
따라서 코드를 아래처럼 개선시킬 수 있습니다. 비교 횟수가 절반 가까이 줄었습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <bits/stdc++.h>
using namespace std;
int arr[1000];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
if (arr[i] < arr[j])
swap(arr[i], arr[j]);
return 0;
}
|
cs |
사족
내림차순으로 정렬하고 싶다면 조건문의 부등호 방향을 바꾸어도 되지만, 두 반복문이 완전히 같으므로 그냥 반복문의 위치를 바꾸기만 해도 됩니다.
이 알고리즘을 처음 접한 사람들은 "이게 될 리가 없지" 또는 "부등호 방향과 반복문을 잘못 썼네" 라고 하겠지만, 놀랍게도 이 알고리즘은 오름차순 정렬을 수행한다.
...
이 알고리즘에는 좋은 점이 없다.
이 알고리즘은 느리고, 비효율적이고, 정당성도 명백하지 않고, stable하지도 않고, ....
유일한 장점은 단순함과 두 반복문의 대칭성일 것이다.
저자는 논문에서 자신의 알고리즘에 대해 이렇게 평가했습니다. 또한 미적인 측면에서 개선된 알고리즘보다 원래 알고리즘을 더 좋아한다고 합니다. 분명 비효율적이지만, 코드 자체도 그렇고 정당성 증명도 그렇고 재미있는 알고리즘인 것 같습니다.