#1517 버블 소트

버블 소트는 정렬에서 가장 재미있는 정렬 방식이자, 사실 실생활에서도 많이 이루어지는 정렬 방식이죠.

 

이웃하는 것끼리 크기를 비교해서 위치가 잘못되었으면 서로 교환을 하는 방식입니다.

 

 

대략 해당되는 알고리즘을 코드로 표현하면 다음과 같습니다.

function Bubble(a, from, to):
	for i in (to, from+1, -1):
    	for j in (from, i-1):
        	if a[j] > a[j+1]: swap(a, j, j+1)

 

위의 알고리즘에서 swap하는 횟수가 몇번인가를 구하는 것이 이번 문제죠.  이 문제를 풀기 위해서 swap 횟수는 몇번 일어날 것인지 알아볼께요.   3, 5, 1, 2, 4  라는 수열이 있습니다.

3

5

1

2

4

이 수열이 버블 정렬에 의해서 swap이 발생하는 과정을 보도록 할께요.

3

1

5

2

4

3

1

2

5

4

3

1

2

4

5

1

3

2

4

5

1

2

3

4

5

총 5번의 swap이 발생했습니다.

3의 입장에서 보면 2번이 발생했고, 5의 입장에서 보면 3번이 발생했죠.

3은 위치 1에서 위치 3으로 이동해서 2번이 움직였고, 5는 위치 2에서 위치 5로 움직여서 3번이 움직였죠.

 

그러면 swap횟수를 카운트하는 방법은,

 

가장 간단한 방법은 버블 정렬을 직접 구현해서 swap(....)할 때 그 수를 카운트해도 되겠지만, 이렇게 하면 버블 정렬 알고리즘 효율이 문제입니다.  버블 정렬 효율은 $O(N^2)$이니까요.

 

두번째로는 모든 숫자에 대해서 뒤에 해당 숫자보다 작은 숫자들을 세는 것입니다.  3의 입장에서는 뒤에 나오는 숫자중 작은 숫자는 1과 2였으므로 2번이 되죠.  5의 입장에서는 1, 2, 4이므로 3번이 되고요.  하지만 이 방법도 알고리즘 효율로 보면 $O(N^2)$이니 버블 정렬하는 것이나 다를 바가 없습니다.

 

세번째 방법은 위치 이동한 것만 따져도 됩니다.  뒤로 움직인 것만 따지면 되는데요.  이것을 잘 활용한다면, 정렬된 곳에서 위치를 찾는 것이니, $O(N\log N)$의 알고리즘으로 따질 수 있습니다.  그런데 이 방법에는 문제가 있습니다.  1, 3, 2, 3, 1, 5 와 같이 중복된 숫자가 있는 경우죠.  3이 어디로 옮겨간 것인지 따지기 위해서는 인덱스 정보를 따로 보관해야 합니다.  (1, 0), (3, 1), (2, 2), (3, 3), (1, 4), (5, 5) 형태로 확장을 해야 합니다.  이렇게 확장을 하면 원하는 숫자가 비록 중복되어 있어도 어느 위치로 갔는지 판단할 수 있습니다.

 

저는 위 방법으로 구현하지 않고, 합병정렬(merge sort)를 이용해서 풀었습니다.  왜 하필이면 합병정렬인가?  일단 $O(N\log N)$ 알고리즘의 고급 정렬중 입력 순서를 지켜주는 정렬은 합병정렬만 있습니다.  위와 같이 인덱스를 따로 준다면, 인덱스의 비교에 의해서도 정렬을 하시면 순서를 지켜주는 정렬이 됩니다.  (3, 1)은 뒤의 (3, 3)보다 인덱스가 앞에 있기 때문에 순서적으로도 앞에 놓이겠죠.  인덱스를 같이 넣은 경우라면 어떤 정렬을 사용해도 괜찮습니다.  모든 값들이 중복이 없이 유일하다는 것을 알 수 있으니까요.  하지만 인덱스 없이 하겠다면 합병정렬이 유일한 방법이고, 합병정렬을 이용하면 합병 과정에서 위치를 판단하여 숫자를 셀 수 있습니다.