배열을 정렬하는 알고리즘은 아주 많은데, 그 중 가장 먼저 배우게 되는 기초적인 알고리즘이 바로 버블정렬(거품정렬)이다. 사실 이 버블정렬 방식의 원리는 무식하기
그지없다. 버블정렬의 원리와 소스를 설명해 보도록 하겠다.
arr[10]이라는 배열이 있다. 이 배열의 원소는 아래와 같다.
8 1 4 14 2 17 48 2 13 48
왼쪽부터 차례로 arr[0], arr[1], arr[2], … , arr[9] 이다. 버블정렬을 통해 이 배열을 오름차순으로 정렬하게 되면 프로그램은 연산을 시작한다.
우선 arr[0]과 arr[1]을 비교한다. arr[0]은 8, arr[1]은 1으로, arr[0]이 arr[1]보다 더 크다. 앞의 원소가 뒤의 원소보다 크므로 이 둘을 서로 바꾸어 준다. 그럼 다시
배열은 아래와 같아질 것이다.
1 8 4 14 2 17 48 2 13 48
이번에는 arr[1]과 arr[2]를 비교한다. arr[1]과 arr[2]는 각각 8과 4로, 이번에도 앞의 원소가 뒤의 원소보다 크다. 그러므로 이 둘을 서로 바꾸어 준다. 배열은 아래와
같은 순서를 가지게 된다.
1 4 8 14 2 17 48 2 13 48
이젠 규칙을 알 것 같은가 ? 이번에는 arr[2]와 arr[3]을 비교한다. 하지만 이미 arr[2]는 arr[3]보다 작으므로, 이 부분에서는 두 수를 서로 바꾸어주지 않는다.
1 4 8 14 2 17 48 2 13 48
다음은 arr[3]과 arr[4]를 비교한다. 14와 2 중 앞의 14가 더 크므로, 두 원소를 서로 바꾸어준다. 그럼 아래와 같은 순서가 된다.
1 4 8 2 14 17 48 2 13 48
이번에는 arr[4]와 arr[5]를 비교할 차례이다. 하지만 여기서 의문이 들 것이다.
“지금 arr[3]에 있는 2는 arr[2]의 8, arr[1]의 4보다 작으니 arr[1]로 가야하는데, 이대로 arr[4]와 arr[5]를 비교하게 되면 2를 그냥 지나쳐 버리지 않나 ? “
확실히 이대로 arr[9]에서 루프가 끝나면 2를 포함한 다른 많은 원소들을 완전히 배열하지 못하게 된다. 하지만 버블정렬은 그래서 버블정렬인 것이다. 루프는 1회가
아닌 9회를 돈다. 즉, 배열의 원소 수만큼 도는 것이다. 위에서 설명한 방식대로 arr[0]부터 arr[9]까지 모든 원소들을 한 번 루프하면 아래와 같은 결과가 된다.
1 4 8 2 14 17 2 13 48 48
그럼 여기서 또 같은 루프를 한 번 더 돈다. 다시 처음의 arr[0]과 arr[1]부터 비교하는 것이다. 루프를 한 번씩 더 돌 때마다 배열은 아래와 같이 바뀌어간다.
루프 1회 :: 1 4 8 2 14 17 2 13 48 48
루프 2회 :: 1 4 2 8 14 2 13 17 48 48
루프 3회 :: 1 2 4 8 2 13 14 17 48 48
루프 4회 :: 1 2 4 2 8 13 14 17 48 48
루프 5회 :: 1 2 2 4 8 13 14 17 48 48 <== 정렬 완료
루프 6회 :: 1 2 2 4 8 13 14 17 48 48
…
루프 9회 :: 1 2 2 4 8 13 14 17 48 48
이제 어째서 루프를 배열의 원소 수만큼 도는지 알 것이다. 이렇게 하지 않으면 완전히 정렬되지 않는 배열도 있기 때문이다. 그 예로 아래와 같은 배열이 있다.
285 112 102 100 58 41 32 13 12 9
이 배열을 위에서 한 것과 같이 루프 횟수에 따라 변화시켜 보면 아래와 같아진다.
루프 1회 :: 112 102 100 58 41 32 13 12 9 285
루프 2회 :: 102 100 58 41 32 13 12 9 112 285
루프 3회 :: 100 58 41 32 13 12 9 102 112 285
루프 4회 :: 58 41 32 13 12 9 100 102 112 285
루프 5회 :: 41 32 13 12 9 58 100 102 112 285
루프 6회 :: 32 13 12 9 41 58 100 102 112 285
루프 7회 :: 13 12 9 32 41 58 100 102 112 285
루프 8회 :: 12 9 13 32 41 58 100 102 112 285
루프 9회 :: 9 12 13 32 41 58 100 102 112 285
최악의 경우 위와 같이 9회째 루프에서 정렬이 완료될 수도 있기 때문에 쓸데없더라도 꼭 끝까지 루프를 실행한다. 그렇기 때문에 버블정렬은 많은 시간을 잡아먹는다.
중간에 이미 정렬이 다 된 것을 확인하기 위해 플래그를 넣어서 무의미한 루프를 빠져나오는 것도 좋은 방법이다. 그렇다면 이제 버블정렬을 사용하는 코드를 작성해
보겠다. 길이가 N인 배열 arr을 오름차순 정렬하기 위한 코드를 작성해 보자.
for(i=0; i<N-1; i++)
{
for(j=0; j<N-i-1; j++)
{
if(arr[j]>arr[j+1]) // 만약 arr[j]가 arr[j+1]보다 큰 경우 아래 연산을 진행한다.
{
int t=arr[j]; // t라는 변수를 선언하고, arr[j]를 변수 t에 대입한다.
arr[j]=arr[j+1]; // arr[j]에 arr[j+1]을 대입한다.
arr[j+1]=t; // arr[j+1]에 t를 대입한다. 앞서 변수 t에는 arr[j]가 대입되어 있으므로 결과적으로 arr[j+1]에 초기의 arr[j]가 오는 셈이다.
}
}
}
버블정렬은 무조건적으로 N개의 배열을 정렬하기 위해 N(N-1)/2 만큼의 연산을 진행하기 때문에, 배열의 크기가 큰 경우에는 쓰지 않는 게 바람직하다. 배열의 크기가
클 때 빠른 정렬을 하기 위해서는 지난번에 포스팅했던 퀵정렬을 쓰길 권장한다.
