버블 정렬 Bubble Sort

Bubble Sort : 거품 정렬

---

• 
  

소개

Bubble Sort는 인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 의 시간복잡도를 갖습니다. 다른 정렬 알고리즘에 비해 속도가 상당히 느린 편이지만, 코드가 단순하기 때문에 자주 사용됩니다.

일반적으로 가장 빠른 정렬 알고리즘은 Quick Sort로 시간 복잡도  입니다.

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble Sort라는 이름을 가지게 되었다고 하네요. 아래 버블 소트의 애니매이션 예시에서 정말 거품 같은지 직접 확인해 보시기 바랍니다.

정렬과정

다음과 같이 다섯 개의 숫자가 주어졌을 때, Bubble Sort로 정렬해 보겠습니다.

이를 배열에 담으면 아래 표와 같습니다.

인덱스	0	1	2	3	4
값	5	3	7	9	1

먼저 5, 3 을 비교했을때 3보다 5가 더 큰 수 이므로, 두 수의 자리를 교체해줍니다.

교체전

인덱스	0	1	2	3	4
값	5	3	7	9	1

교체후

인덱스	0	1	2	3	4
값	3	5	7	9	1

다음 오른쪽으로 한칸 이동하여 5와 7을 비교합니다. 여기서는 이미 큰 수 (7) 가 뒤에 있으므로 교체하지 않습니다.

인덱스	0	1	2	3	4
값	3	5	7	9	1

다시 오른쪽으로 한칸 이동하여 7와 9을 비교합니다. 여기서도 이미 큰 수 (9) 가 뒤에 있으므로 교체하지 않습니다.

인덱스	0	1	2	3	4
값	3	5	7	9	1

다시 오른쪽으로 한칸 이동하여 9와 1을 비교합니다. 9가 1보다 더 큰 수 이므로, 두 수의 자리를 교체해 줍니다.

교체전

인덱스	0	1	2	3	4
값	3	5	7	9	1

교체후

인덱스	0	1	2	3	4
값	3	5	7	1	9

자, 한번의 순회가 끝났습니다. 이 알고리즘의 이름이 왜 Bubble Sort인지 이제 조금 아시겠나요?

모든 원소를 한 번씩 들러본 결과, 다섯개의 숫자 중 가장 큰 수인 9가 파도처럼 밀려 맨 마지막, 즉 정렬이 완료 되었을 때의 자신의 자리를 찾아갔습니다.

여기서 다음번 순회 부터는 모든 원소를 방문할 필요가 없다는 것을 아시겠나요? 가장 큰 수 9는 정렬 된 후 자신이 있어야할 위치에 도착했기 때문입니다.

위와 같은 과정이 한차례 진행될 때마다, 뒤에서 부터 정렬이 완료된 원소들이 하나씩 위치하게 되는 것을 볼 수 있습니다. 정렬이 완료된 원소들은 다시 정렬 될 필요가 없겠죠?

따라서 두 번째 순회 부터는 이미 정렬이 완료된 원소들을 제외한 원소들만 방문하여 정렬해 주면 됩니다.

이제 나머지 원소들의 자리도 찾아주기 위해 9를 제외한 원소들을 처음부터 다시 반복하여 비교해 봅시다.

인덱스	0	1	2	3	4
값	3	5	7	1	9

3, 5 를 비교했을때 이미 큰 수( 5 ) 가 뒤에 있으므로 자리를 교체하지 않습니다.

인덱스	0	1	2	3	4
값	3	5	7	1	9

다음 오른쪽으로 한칸 이동하여 5와 7을 비교합니다. 이미 큰 수( 7 ) 가 뒤에 있으므로 교체하지 않습니다.

인덱스	0	1	2	3	4
값	3	5	7	1	9

다시 오른쪽으로 한칸 이동하여 7와 1을 비교합니다. 7가 1보다 더 큰 수 이므로, 두 수의 자리를 교체해 줍니다.

교체전

인덱스	0	1	2	3	4
값	3	5	7	1	9

교체후

인덱스	0	1	2	3	4
값	3	5	1	7	9

두 번째 순회가 완료 되었습니다. 남은 네 개의 원소 중 가장 큰 수인 7이 자신의 자리를 찾아갔네요! 

나머지 세 개의 원소들을 다시 처음부터 순회해 줍니다.

인덱스	0	1	2	3	4
값	3	5	1	7	9

3, 5 를 비교했을때 이미 큰 수( 5 ) 가 뒤에 있으므로 자리를 교체하지 않습니다.

인덱스	0	1	2	3	4
값	3	5	1	7	9

다음 오른쪽으로 한칸 이동하여 5와 1을 비교합니다. 5가 1보다 더 큰 수 이므로, 두 수의 자리를 교체해 줍니다.

교체 전

인덱스	0	1	2	3	4
값	3	5	1	7	9

교체 후

인덱스	0	1	2	3	4
값	3	1	5	7	9

계속 같은 방식으로 세 번째 순회를 시작합니다.

인덱스	0	1	2	3	4
값	3	1	5	7	9

3, 1를 비교했을때 1보다 3이 더 큰 수 이므로 자리를 교체해 줍니다.

교체 전

인덱스	0	1	2	3	4
값	3	1	5	7	9

교체 후

인덱스	0	1	2	3	4
값	1	3	5	7	9

이후의 과정도 위의 방식처럼 진행하게 됩니다.

인덱스	0	1	2	3	4
값	1	3	5	7	9

여기서는 이제 정렬이 끝났으므로 생략하도록 하겠습니다.

이제 Bubble Sort가 어떻게 작동하는지 아시겠나요? 
원소들이 큰 순서대로 뒤로 밀려가 거품처럼 정렬되는 모습을 볼 수 있었습니다.

알고리즘 분석

다음으로 시간복잡도를 알아봅시다.

1. 비교 횟수

   버블 정렬은 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에, 전체 원소의 개수가 n개 라고 할 때, 총 n-1 번 순회하면 정렬이 끝납니다. 위의 예제에서는 총 원소 개수가 5개 이므로, 4 + 3 + 2 + 1 = 10번 비교하게 됩니다. 이를 수식으로 일반화 시키면 다음과 같습니다.

2. 자리 교환 횟수

   최선의 경우 ( 이미 정렬된 원소들이 주어진 경우 ) , 자리 교환이 한번도 이루어 지지 않으므로, 시간복잡도에 영향을 미치지 않게 됩니다.

   하지만 최악의 경우 ( 역순으로 정렬된 원소들이 주어진 경우 ), 원소를 비교 할 때마다 자리 교환이 일어나므로, 자리 교환 횟수 또한 비교 횟수와 같이  가 됩니다.

따라서 평균적으로  의 시간복잡도를 가지게 됩니다.

애니매이션 예시

위키백과에서 만든 애니매이션과 또 다른 동영상예시를 첨부합니다. 동영상 예시를 보시면 더 재미있게 Bubble Sort를 이해하실 수 있습니다. 원소들이 춤을 추거든요

1. 위키백과 예시

출처 위키백과

위 애니메이션의 y축은 수의 크기, x축은 원소의 인덱스를 나타냅니다. 큰 수부터 거품처럼 밀려 제 자리를 찾아 정렬되는 것을 볼 수 있습니다.

2. 동영상예시 
   …

구현

코드는 굉장히 간단합니다. 위에서 순회할 원소의 개수가 하나씩 줄어든다는 점을 기억 하셨다면 쉽게 이해하실 수 있습니다.

int main()
{
    int N = 5; //배열의 길이
    int i, j, temp;
    int data[] = { 5, 3, 7, 9, 1 };

    // Bubble Sort 
    for (i = 0; i < N; i++) {
        for (j = 0; j < N-(i+1); j++) {
            if (data[j] > data[j+1]) {
                // 자리교환
                temp = data[j+1];
                data[j+1] = data[j];
                data[j] = temp;
            }
        }
    }
}

정리

Bubble Sort는 이처럼 이해하기도 쉽고 코드도 단순하지만, 이라는 시간복잡도 때문에 비교할 데이터의 개수가 많을 수록 성능이 저하됩니다.

예제에서는 원소의 개수가 5개 뿐이라 10번의 연산만 하면 되었습니다. 
하지만 데이터의 개수가 만 개만 되어도 무려 약 오천만 번의 비교 연산을 필요로 하기 때문에 Bubble Sort는 데이터의 개수가 적은 경우에 주로 사용하게 됩니다.

추가적으로 Bubble Sort 를 개선하는 코드를 구글링 해보시면 도움이 됩니다. ( 최선의 경우 비교 자체를 시작 하지 않게, 최악의 경우 뒤에서 부터 정렬 등등..)

끝

출처: http://bowbowbow.tistory.com/10