Bubble Sort - 거품 정렬과 코드

지금까지 내가 알고있기로는 버블 소트는

앞으로 다룰 정렬중에서 가장 정직하고(?) 가장 비효율적인 정렬이다.

그래서 이 정렬이 실제로 쓰이는지 궁금하기도하다.

 

오름차순의 경우, 거품 정렬은 뒤에 있는 데이터와 값을 비교하면서 

앞의 데이터가 뒤의 데이터보다 크면 위치를 교환한다.

 

처음에는 주어진 배열의 처음에서 끝(N)까지 탐색,

그 뒤로는 처음부터 N-1까지 탐색, 그 뒤로는 N-2까지 탐색하며 탐색 범위를 줄여나간다.

 

그래서 처음 탐색을 완료하면 N번째에는 제일 큰 수가 오고

다음으로 탐색을 완료하면 N-1번째에는 그 다음으로 큰 수가 온다.

 

예를 들어 1, 5, 3, 2, 4 라는 배열이 있을 때

이를 거품정렬을 한다면

다음과 같을 것이다.

 

 

이 과정을 의사코드로 나타내면

for(int i = 0; i < N-1 ; i++) {
	for(int j = 0; j< N-1-i; j++) {
    	if(arr[j] > arr[j+1]){
        	swap(arr[j], arr[j+1]);
        }
    }
}

위와 같이 나타낼 수 있다. N-1번 반복하는 과정속에서

0부터 N-1-i까지 비교하며 진행하게 된다.

 

C언어로 간단히 구현해보면

#include <stdio.h>
#include <string.h>

void swap(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

//오름차순 order 1, 내림차순 order -1
void bubble_sort(int n, int order, int arr[]){
    int i,j;
    for(i = 0; i < n-1; ++i){
        for(j = 0; j < n-1-i; ++j){
            if(order*arr[j] > order*arr[j+1]){
                swap(&arr[j], &arr[j+1]);
            }
        }
    }
}

int main(void)
{
    int i;
    int arr[10];
    for(i = 0; i < 10; ++i){
        scanf("%d", arr + i);
    }
    bubble_sort(10, 1, arr);

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

위와 같다.

 

어떤 상황에서든 N에 가까운 2번의 반복문을 거치기 때문에

거품정렬의 시간복잡도는 최선/평균/최악 모두 n^2 이다.