버블 정렬(Bubble sort)

정렬 알고리즘의 한 종류인 버블 정렬에 대해 알아보겠다.

 

Bubble sort?

 

버블 정렬이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

인접한 2개의 레코드를 비교하여 크기가 순서대로(ex. 오름차순 또는 내림차순) 되어 있지 않으면 서로 교환한다.

버블 정렬 알고리즘에대해 구체적인 개념을 살펴보면 아래와 같이 요약할 수 있다.

 

• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를,... 이런 식으로 (마지막 -1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외하고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
• 일반적으로, 각 i번째 회전이 끝난 후, 우측에서 i개의 원소들은 (즉, 인덱스 n-1부터 n-i까지의 원소들) 그들의 최종 위치에 도달한 것이다.
• n개의 원소들을 버블 정렬을 통해 정렬할때 패스들의 개수를 n으로 제한한다. 그리고 이것은 i번째 회전이 처음 n-i+1개의 원소들만을 사용하도록 허용한다.

버블 정렬 분석

 

원소의 접근과 원소들의 교환이 각각 O(1) 시간이 걸리도록 구현되었다고 가정하자. 이때, i번째 회전의 실행 시간은 O(n-i+1)이다. 즉, 버블 정렬릐 전체 실행 시간은

이다. 위의 big-Oh 표현식 내의 합은 아래와 같이 다시 쓸 수 있다.

위의 합은 다음과 같이 다시 쓸 수 있다.

그러므로, 원소의 접근과 교환이 각각 O(1) 시간 내에 수행되게 구현된다면 버블 정렬은 O(n^2)시간에 실행된다.

 

버블 정렬 알고리즘 실행 예제

 

 

버블 정렬 예제

• 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--){
    // 0 ~ (i-1)까지 반복
    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]);
  }
}

 

버블 정렬 알고리즘의 특징

 

• 장점
  • 구현이 매우 간단하다.
• 단점
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다. 특히, 특정 요소가 최정 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다. 즉, 자료의 교환 작업이 복잡하기 때문에 거의 쓰이지 않는다.