[Data Structure] 버블 정렬(bubble sort)

---

버블 정렬

 

 

정렬할 때 큰 수를 뒤로 미루는 것 때문에 거품이 올라오는 것 같아 이름 붙여진 정렬 방식이다. 효율적이지는 않지만, 구현이 쉽고, 가장 쉽게 생각할 수 있는 정렬 방식이다.

정렬은 인접한 두 수를 선택한 후 비교하고, 큰 수가 앞에 있다면 두 수를 교환하는 방식이 반복되며 일어난다. 첫번째 수와 두번째 수를 선택한 후 비교, 교환하고, 두번째 수와 세번째 수를 선택한 후 비교, 교환하고, ... 반복하여 마지막 수에 도달한다면 가장 큰 수가 가장 마지막 자리에 도달하게 된다.

이제 다시 첫번째 수와 두번째 수를 선택한 후 비교, 교환하고, 두번째 수와 세번째 수를 선택한 후 비교, 교환하고, .. 반복하여 마지막 수 앞 칸에 도달하면 뒤 두 수가 정렬된다. 앞선 정렬을 통해 마지막 수가 정렬되었고, 이 과정을 통해 마지막 수 직전 수가 정렬되었다.

같은 방법을 정렬해야 하는 리스트의 길이보다 1 작게 실행한다면 모든 수가 정렬될 것이다.

 

---

예시

 

예를 들어 위와 같은 리스트를 정렬한다고 해보자.

먼저 위와 같이 가장 앞 두 수를 선택하여 비교한다. 앞의 수 9가 뒤의 수 2보다 크다.

그러므로 두 수의 자리를 바꿔준다. 그 후 아래와 같이 두번째 자리로 이동하여 비교하고 교환한다.

$$ \vdots $$

반복하여 가장 뒤 수를 정렬하였다.

다시 반복하여 수를 정렬한다.

$$ \vdots $$

반복하면 위와 같이 정렬되었다. 이 과정을 리스트의 크기가 $ n $ 이라 할 때 $ n - 1 $ 번 반복하면 정렬이 끝난다.

예시에서 보이듯이 버블 정렬은 오름차순으로 정렬한다 할 때 큰 수부터 정렬하는 특징이 있고, 정렬 중 정렬이 완료되었는지 확인하지 않기 때문에 정렬 상태와 관계없이 같은 횟수의 비교, 교환을 반복한다.

루프를 두 번 반복하므로 버블 정렬의 시간복잡도는 정렬 상태와 관계없이 $ \mathcal{O}(n^2) $ 이다.

 

---

구현 | C

 

void bubble_sort(int list[], int n) {
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (list[j] > list[j+1]) {
                int temp = list[j];
                list[j] = list[j+1];
                list[j+1] = temp;
            }
        }
    }
}