[알고리즘] 버블정렬(Bubble Sort)이란?

버블정렬이란

• 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환하는 방식의 정렬 알고리즘
• 선택정렬과 기본개념이 유사하다

---

버블정렬 기본 개념

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

---

 

버블정렬 과정

1. 첫번째 자료 7을 4와 비교하여 교환하고, [교환]칸이 한 칸 이동되어 7과 5를 교환, 7과 1을 교환 이런식으로 교환해나가면 맨 마지막 자료에는 7이 삽입되고 7은 정렬완료 상태
2. 마찬가지로 5가 1번처럼 7 한 칸 앞에 삽입되어 5 7 은 정렬완료 상태
3. 4가 5 7 앞에 삽입되어 4 5 7 은 정렬 완료 상태
4. 1과 3은 그대로 유지되고 3 4 5 7은 정렬 완료 상태

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

int main() {
    int arr[5] = {9,6,7,3,5};
    int i,j;
    for(i=4; i>0; i--){
        for(j=0; j<i; j++){
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

    for(int i=0; i< 5;i++){
        printf("%d ", arr[i]);
    }

}

---

 

버블정렬 특징 및 시간복잡도

장점

• 구현이 매우 간단하다

단점

• 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
• 특정 요소가 최종 정렬위치에 이미 있는 경우라도 교환되는 일이 발생할 수 있다.
• 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에 불구하고 거의 쓰이지 않는다.

---

시간복잡도

비교회수는 최상평균최악 모두 일정

이동횟수

입력 자료가 역순으로 정렬되어 있는 최악의 경우, 

한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2

입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.

O(N^2)

---