버블정렬 (Bubble Sort)

버블 정렬(bubble sort) 의 개념 요약

서로 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하며 정렬해나가는 알고리즘이다.

 

구체적인 개념

• 버블 정렬은 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째와 네 번째를, … 이런 식으로    (마지막-1)번째 원소와 마지막 원소를 비교하여 교환하면서 정렬한다.
• 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

예제

→ 배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 오름차순으로 정렬해 보자.

 

• 1회전
  첫 번째 원소 7을 두 번째 원소 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 원소를 네 번 비교한다. 그리고 가장 큰 원소가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 원소는 비교할 필요가 없다.
• 2회전
  첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 원소를 세 번 비교한다. 비교한 원소 중 가장 큰 원소가 끝에서 두 번째에 놓인다.
• 3회전
  첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 원소를 두 번 비교한다. 비교한 원소 중 가장 큰 원소가 끝에서 세 번째에 놓인다.
• 4회전
  첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.

 

 

c언어 코드

# include <stdio.h>
# define MAX_SIZE 5

// 버블 정렬
void bubble_sort(int list[], int n){
  int i, j, temp;

  for(i=n-1; i>0; i--){
  // 배열크기보다 -1만큼 회전을 돔 (배열크기 5라면 4회전)
    for(j=0; j<i; j++){
      // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
      if(list[j]<list[j+1]){
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {7, 4, 5, 1, 3};

  // 버블 정렬 수행
  bubble_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

 

 

특징

• 장점
  - 구현이 매우 간단하다.
• 단점
  - 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
  - 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
  - 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하고 느리기 때문에 단순성에도 불구하고 거의 쓰이지 않는다.

 

안정성 & 제자리성

버블정렬 알고리즘으로 정렬을 수하는 경우, 원소들의 본래 순서가 거의 유지된 채 정렬된다. 따라서 버블정렬은 안정정렬(Stable Sort)이다. 또한, 기존 배열 이외의 추가적인 메모리를 거의 사용하지 않는 제자리 정렬(In-place sort)이다.

 

시간복잡도

첫 번째 사이클 (i == n-1)에서 비교 횟수 0 ~ (n-2) : N-1회

두 번째 사이클 (i == n-2)에서 비교 횟수 0 ~ (n-3) : N-2회

.

.

.

마지막 회전(i == 1)에서 비교 횟수 : 1회

 

(N-1) + (N-2) + (N-3)... + 1 = N(N-1)/2

즉 시간 복잡도는 O(N^2)이다.

 

 

버블 정렬에서 시간복잡도 최적화하기

버블 정렬은 두 원소를 비교하여 교환을 하지 않더라도, 배열 크기만큼 비교는 계속 진행하기에 항상 어떤 경우에도 O(n^2)의 시간복잡도를 갖는다. 그렇기 때문에 이미 정렬된 배열이 들어오더라도 똑같은 O(n^2)의 시간복잡도가 나온다.

 

그래서 처음부터 정렬된 배열이 들어오거나, 혹은 버블 정렬 진행 중간에 정렬이 완성 되는 경우, 더 이상 비교를 진행하지 않고 결과를 바로 반환하도록 하여 시간 복잡도를 최적화시킬 수 있다.

 

예를 들어 처음 for문을 돌 때마다 초기 카운트를 0으로 지정하고, 교환이 일어난다면 카운트가 1씩 증가하게 한다.

만약 배열을 한번 다 비교 했을 때, 카운트가 0이라면 (즉, 교환이 1번도 일어나지 않았다면) 그 배열은 이미 정렬이 다 되어있는 배열이라고 생각할 수 있다. 이때 정렬을 중지하고 (for문을 빠져나옴, break) 그 상태의 배열을 바로 반환하면 된다.

 

이렇게 최적화를 하게 되면 best case (처음부터 정렬된 배열이 들어올 경우)는 처음 한번만 배열의 원소들을 비교하고, 교환이 한번도 일어나지 않았기 때문에 바로 그 상태의 배열을 반환하게 되고 이때의 시간복잡도는 O(n)이 나오게 된다.

(중간에 정렬이 완성되는 경우에도 언제 정렬이 완성될지 모르겠지만, O(n^2)보다는 좀 더 나을 것이다)