버블 정렬

버블 정렬(Bubble Sort)

---

 버블 정렬은 O($n^2$)의 복잡도를 가진 대표적인 알고리즘이다. 

비교 정렬이면서 제자리 정렬 방식으로, 한 번 돌 때마다 마지막 하나가 정렬되어 원소들이 거품처럼 올라온다는 의미이다.

 거의 모든 상황에서 최악의 성능을 보여주나, 이미 정렬된 자료에서는 최선의 성능이 나온다.

 가장 생각하고 이해하기 쉬워서 각종 교습서에 예시로 많이 보여지고 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 대단히 비효울적인 정렬 방식이므로 실제 개발에선 사용되지 않는다.

정렬 방법(오름차순)

---

 배열의 모든 원소에 대해서 인접한 두 원소를 비교하며 앞 원소가 뒤 원소보다 비교하는 값이 클 경우 위치를 교환하면 된다.

 $1$번 원소와 $2$번 원소, $2$번 원소와 $3$번 원소 $...$ $n-1$번 원소와 $n$번 원소를 비교하면 총 $n-1$회 비교하게 되는데, 한 번 수행했을 경우 가장 큰 원소가 필연적으로 가장 뒤에 위치하게 되므로 다음 수행의 비교 횟수는 1회 줄어든다. 그러면 첫 수행 시 $n-1$회 그 다음 수행 $n-2$회 $...$ 최종 수행 시 $1$회 비교하게 되어 최악의 경우 $\frac{n(n-1)}{2}$회 비교한다.

▶ 과정을 순서대로 표현하면 다음과 같다.

1. 주어진 배열의 $i$번째와 $i+1$번째를 비교-교환한다.
2. $i$를 $n-1$이 될 때까지 1씩 더하며 반복한다.
3. 다시 $i$를 $0$으로 초기화하고 $n$를 $n-1$로 초기화한다.
4. $n==1$이 될 때까지 반복한다.

그림과 함께 수행 과정을 살펴보자.

위와 같이 8개의 원소가 임의의 순서로 저장된 배열이 있다.

$1$번 원소와 $2$번 원소 비교와 $2$번 원소와 $3$번 원소를 비교는 모두 앞 원소가 뒤 원소보다 작으므로 교환하지 않는다.

하지만 $3$번 원소와 $4$번 원소의 경우 앞 원소가 뒤 원소보다 크므로 두 원소의 위치를 위 그림처럼 교환해준다.

그 후 $4$번 원소와 $5$번 원소도 똑같이 자리를 바꾼다.

계속해서 $5$번, $6$번 등에도 비교-교환을 수행하게 되면

 $1001$이 이 배열에서 가장 큰 값이므로 결국 오른쪽 끝으로 이동하게 된다.

이렇게 되면 오름차순 정렬에서 가장 큰 원소의 자리가 잡힌 것이므로 더이상 포함시키지 않아도 된다.

마지막 원소를 제외하고 다음 $n-1$개의 원소에 대해서 각각 비교-교환 수행을 하면,

두 번째로 큰 $338$이 제일 뒤로 가게 되고 그 자리는 고정되게 된다.

계속해서 비교-교환을 수행하면

이 경우에 총 6번의 반복을 수행하면 위와 같이 정렬되는데 

나머지 2개의 원소는 더이상 비교-교환을 할 필요가 없고, 정렬이 완료된 상태이다.

만약에 위 그림처럼 애초에 정렬이 되어있는 배열에 대해서 버블 정렬을 수행하면 단 한 번도 교환을 하지 않기 때문에

O($n$)의 시간 복잡도를 가지게 되지만, 예제와 같이 일반적인 경우 O($n^2$)의 시간 복잡도이여서 비효율적이다.

하지만 그림에서 보는 것과 같이 이해하고 구현하기 쉽기 때문에 매우 간단한 문제를 빨리 해결하기 위해선 사용해볼 만하다.

소스코드

---

 간단한 알고리즘인 만큼 소스코드 또한 간결한데, C언어를 사용하여 구현한 코드를 게시하여 보겠다.

#include<stdio.h>
#define LEN 8
#define INF 0xFFFFFFF
 
void Swap(int *a, int *b){ // 두 수를 바꾸는 함수
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void PrintArray(int *arr, int len){ // 배열 값들을 출력하는 함수
    for(int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
void Bubble_Sort(int *arr, int len){ // 버블정렬
    for(int i = 0; i < len - 1; i++){
        for(int j = 0; j < len - i - 1; j++){
            if(arr[j] > arr[j + 1]) // j번째 인덱스 값보다 j + 1번째 인덱스 값이 작으면
                Swap(&arr[j], &arr[j + 1]); // 그 두 수를 바꾸어 줌.
        }
        PrintArray(arr, len);
    }
}
 
int main(){
    int arr[] = {68, 126, 1001, 2, 138, 338, 168, 58};
    Bubble_Sort(arr, LEN);
    return 0;
}

 이 글은 제가 공부하면서 이해한 부분을 정리한 것입니다.

 틀린 부분이 있다면 댓글로 피드백 해주시고 도움이 되셨다면 추천과 공감 부탁드리겠습니다.

출처 : 나무위키(정렬 알고리즘)