버블 정렬

버블정렬

 

버블 정렬이란?

거품이 보글보글 올라오는 모양처럼 정렬이 일어난다고 해서 버블 정렬이다.

버블 정렬은 '이웃끼리' 교환을 통해 요소를 정렬한다.

한 사이클을 순회할 때 마다 '가장 큰 수'가 자리를 잡게 된다.

 

예시

5 1 6 4 2 3

제일 왼쪽에 있는 요소 부터 이웃 데이터끼리 비교하여 오름차순으로 정렬한다.

 

5와 1을 비교한다.

1 5 6 4 2 3

 

5와 6을 비교한다. 교환이 필요없으므로 넘어간다.

6과 4를 비교한다.

1 5 4 6 2 3

 

6과 2를 비교한다.

1 5 4 2 6 3

 

6과 3을 비교한다.

1 5 4 2 3 6

 

한 사이클이 끝나면, 가장 큰 수가 가장 마지막에 자리를 잡을 수 있다.

보글보글 하면서 가장 큰 수가(6) 마지막에 가 있고.

그 다음 사이클에는 또 보글보글 하면서 그 다음 큰 수(5)가 마지막에 가 있고.

그 다음 사이클에는 보글보글 하면서 그 다음 큰 수(4)가 마지막에 가 있고. ... 를 반복하게 된다.

 

---

얼마나 빠를까

데이터를 순회할 때 마다 순회할 데이터의 개수가 1개씩 줄어든다.

데이터 요소가 N개라면, n-1회, n-2회, n-3회 ... 1회.

따라서 n-1 부터 1까지의 합을 구하면 버블 정렬의 비교연산 횟수가 된다.

오래걸리지만 구현은 간단하다는 장점이 있다.

 

선택정렬의 경우, 한 사이클을 돌면서 교환(Swap)을 딱 1번만 한다. 

교환 할 요소의 인덱스를 기억해 두었다가 내부 for문이 종료되면 교환을 1번 하기 때문이다. 

반면 버블정렬은 가장 큰수를 가장 마지막 자리로 보내는데에 1번 이상이 필요하다.

버블 정렬은 시간 복잡도가 매우 큰 정렬 방식이다. 

---

버블정렬 코드

 

#include <stdio.h>

void BubbleSort(int dataset[], int num){ // 배열과 배열길이를 입력받음

    int i = 0, j=0, temp = 0;
    
    for(i=0; i<num-1; i++){ // num-1 만큼 순회  
        
        for(j=0; j<num-(i+1); j++){ // 정렬할 요소가 1개씩 줄어든다 
            
            if(dataset[j] > dataset[j+1]){ // 교환 조건
                temp = dataset[j];
                dataset[j] = dadtaset[j+1];
                dataset[j+1] = temp;
            }
        }
    }
}

int main(){
    
    int dataset[] = {10, 5, 1, 15, 4, 8, 9};
    int num = sizeof(dataset) / sizeof(dataset[0]);
    int i = 0;
    
    BubbleSort(dataset, num);
    
    for(i=0; i<num; i++){
        printf("%d ", dataset[i]);
    }
    
    return 0;
}