Bubble Sort

버블 정렬은 간단한 코드 때문에 입력이 크지 않은 경우 많이 사용된다. 이 정렬 알고리즘은 첫번째부터 N번째까지 차례대로 보면서 만약 인접한 두 값이 역순일 경우 바꾼다. 이걸 N번 반복하면 수열이 정렬된다. 이것은 이 알고리즘을 한 번 실행할 때마다 가장 큰 원소가 제자리로 가기 때문에 N번 후에는 모든 수열이 정렬됨을 알 수 있기 때문이다.

이것을 코드로 구현하면 다음과 같다.

void BubbleSort(int N,int a[]){
	for(int i=0;i<N;i++){
		for(int j=1;j<N-i;j++){
			if(a[j-1]>a[j]){
				swap(a[j-1],a[j]);
			}
		}
	}
}

두번째 for문에서 N번째 원소까지 보는 것이 아니라 N-i번째 원소까지만 보는 이유는 그 뒤의 원소들은 정렬할 필요가 없음이 보장되기 때문이다. 하지만 그렇다고 시간복잡도에 변화는 없고 여전히 \(\BigO{N^2}\)이다.

버블 정렬에 관한 문제에서 자주 다루어지는 요소는 교환 횟수이다. 교환수라고도 불리는 이 숫자는 정렬에서 중요하게 다루어지는 수이다. swap함수가 정렬 하는 중에서 얼마나 많이 호출되는지 구하는 것은 버블 정렬을 실행하며 세면 되지만 N이 많이 큰 경우에는 이것이 불가능하다. N이 큰 입력에서도 교환수를 구하려면 교환수가 가지는 성질을 알아야 한다.

정렬되지 않은 수열에는 세가지 종류의 수들이 있다. 원래 위치보다 앞에 있는 수, 제자리에 있는 수, 뒤에 있는 수이다. 여기서 원래 위치보다 앞에 있는 수를 A, 뒤에 있는 수를 B라고 하겠다. 한 번 swap함수가 호출되면 A는 한 칸 뒤로 가고 B는 한 칸 앞으로 간다. 이 때문에 수열에 존재하는 모든 A들이 총 뒤로 간 횟수를 세면 교환수를 구할 수 있다. 하지만 각 A가 얼마나 뒤로 가는지 구하기는 어렵다. 어떤 A가 자신 보다 앞에 있으면서 더 큰 A를 만나면 앞으로 갈 수도 있기 때문이다. 이 때문에 현재 있는 위치로 A가 얼마나 뒤로 가는지 계산할 수는 없고 A가 얼마나 많은 수들을 제치고 뒤로 이동하는지를 구해야 한다. 어떤 수를 통과하는 A가 몇 개인지 세보자. 모든 수에 대해서 자신을 지나치는 A의 개수를 알고 있다면 그 수들의 합이 총 A가 이동한 거리이고 교환수이다.

만약 i번째 수\(\left(a_{i}\right)\) 앞에 있는 수 중에서 \(a_{i}\)보다 큰 숫자가 없다면 A들 중에서 \(a_{i}\)를 지나치는 수는 존재하지 않는다. 그러나 \(a_{i}\)앞에 \(a_{i}\)보다 큰 숫자가 있으면 그 큰 숫자(A)가 뒤로 이동할 때 \(a_{i}\)를 지나치며 swap함수를 호출할 것이다. 만약, 모든 \(a_{i}\)들에 대해서 자기 보다 앞에 있으면서 큰 수(역순인 수)가 몇 개 있는지 알 수 있다면 이 수들의 합을 구해서 교환수를 구할 수 있다.

\(a_{i}\)와 역순인 수를 \(\BigO{N}\)에 확인할 수도 있지만 그러면 버블 정렬을 실행하는 것보다 나은 점이 없다. 인덱스 트리를 사용하여 \(\BigO{\log N}\)만에 이 수를 구할 수 있다. 먼저 좌표압축을 하여 모든 수들을 \(\left[0,N\right)\)범위에 들어오도록 만든다. 인덱스 트리의 인덱스를 수의 크기로 하고 0부터 \(a_{i}\)까지 합을 구할 수 있게 하면 \(a_{i}\)와 역순인 수의 개수는 i에서 \(a_{i}\)까지의 합을 뺀 것이고 인덱스 트리의 \(a_{i}\)번째 노드에 1을 더하면 \(a_{i+1}\)와 역순인 수의 개수도 쉽게 구할 수 있다. 다음은 이를 구현한 코드이다.

struct BIT{
	vector<long long> tree;
	BIT(int n):tree(n+1){}
	
	void add(int x,long long c){
		x++;
		while(x<tree.size()){
			tree[x]+=c;
			x+=x&-x;
		}
	}
	
	long long sum(int x){
		x++;
		long long ret = 0;
		while(x>0){
			ret+=tree[x];
			x-=x&-x;
		}
		return ret;
	}
};

void compress(int N,int a[]){
	vector<int> b(N);
	for(int i=0;i<N;i++){
		b[i]=a[i];
	}
	sort(b.begin(),b.end());
	b.erase(unique(b.begin(),b.end()),b.end());
	for(int i=0;i<N;i++){
		a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin();
	}
}

long long InversionNumber(int N,int a[]){
	compress(N,a);
	BIT bit = BIT(N);
	
	long long ret = 0;
	for(int i=0;i<N;i++){
		ret += (long long)(i-bit.sum(a[i]));
		bit.add(a[i],1ll);
	}
	return ret;
}

다음은 버블 정렬에 관한 재미있는 문제들이다.

• 버블 정렬의 교환수와 관련된 문제 중 생각해 볼만한 문제로는 JOI 2013 5번 문제인 バブルソート가 있다. 이 문제는 주어진 수열에서 두 수를 골라 위치를 바꿀 때 만들 수 있는 최소의 교환수를 찾는 것이다. 자료구조에 자신이 있다면 풀어보길 바란다. (https://www.acmicpc.net/problem/5531)
• 버블 정렬의 중간 단계를 구하는 문제도 있다. 버블 정렬이 어떻게 동작하는지 잘 이해하고 있어야한다. (https://www.acmicpc.net/problem/11920)
• 마찬가지로 버블 정렬이 어떻게 동작하는지 이해하면 풀 수 있는 문제이다. (https://www.acmicpc.net/problem/1838)