[알고리즘] 1_2. 버블정렬(Bubble Sort)

1. 정의

버블 정렬(Bubble Sort)은 정렬될 때 그 모습이 마치 거품이 위로 하나씩 오르는 듯하다고 해서 이름이 붙여졌다. 원리와 코드가 간단하기 떄문에, 정렬 알고리즘을 배울 때 많이 쓰이는 듯 하다. 버블 정렬의 가장 중요한 원리는 다음과 같다.

- 인접한 두개의 데이터를 비교해 가장 큰(혹은 작은) 데이터를 오른쪽에 오도록 위치를 바꾼다.

위 과정을 반복하면, 가장 오른쪽에는 가장 큰(혹은 작은) 데이터부터 쌓이게 된다. 이를 이용해 데이터를 정렬하는 과정을 버블 정렬(Bubble Sort)라고 한다.

2. 설명

PASS 1

버블 정렬은 항상 인접한 두개의 데이터를 비교해가며, Swap을 통해 자료를 정렬한다. 그 순서를 보면 다음과 같다.

우선 2 와 3 을 비교해본다. 3 이 2 보다 크므로 두 데이터의 위치를 바꾼다.

마찬가지로, 3 과 1 을 비교해본다. 3 이 1 보다 크므로 위치를 바꾸어 준다.

3 과 5 를 비교했을 때, 3 은 5 보다 작으므로, 그대로 유지한다.

5 와 4 를 비교했을 때, 5 가 4 보다 크므로, 위치를 바꾸어 준다.

PASS 1이 끝난 모습이다. 하나의 PASS가 끝날 때마다, 가장 뒷부분은 비교했던 수 중 가장 큰 수로 채워지게 된다. PASS 1에서 비교한 5개의 데이터 중 5가 가장 컸으므로, 5가 가장 뒤에 오게 되는 것이다. 이렇게 가장 큰 숫자가 뒤로 오는 모습이 거품이 오르는 모습과 비슷하다고 해서 버블 정렬이라는 이름을 가지게 된 것이다.

PASS 2

5 는 이미 정렬된 데이터이므로 앞의 2, 1, 3, 4 네개만 비교하면 된다. 그 비교하는 과정은 PASS 1과 동일하게 진행된다.

이 데이터는 PASS 2 에서 완전히 정렬되게 되며( 하지만 반복문은 종결되지 않는다. 남은 과정은 데이터의 비교일 뿐, Swap과정은 존재하지 않는다.), 그 결과는 다음과 같다.

3. 코드

for(i=0;i<Len-1;i++){//Len은 정렬할 데이터 수
    for(j=0;j<Len-1-i;j++){
        if(data[j]>data[j+1]){
          int temp=data[j];
            data[j]=data[j+1];
            data[j+1]=temp;
        }
    }
}

다른 정렬 알고리즘 보기