[알고리즘 공부] 버블 정렬(Bubble Sort)

정렬(整列)은 항목들을 체계적으로 정리하는 과정으로, 순서를 정하는 것이라는 사전적 의미가 있다. 즉, 순서를 정하는 알고리즘이 정렬 알고리즘이라고 할 수 있다. 그 중에서 오늘은 버블 정렬(Bubble Sort)에 대해서 공부하고자 한다.

 

버블 정렬

성능

버블정렬에서 버블은 원소들이 거품이 올라오는 것처럼 보이기 때문에 붙은 이름이라고 한다. 버블정렬은 구현하기는 쉽지만 최악의 정렬 알고리즘이다. 거의 모든 상황에서 O(n^2)의 시간복잡도를 보여주기 때문이다. 즉, 정렬할 자료의 수의 제곱에 비례해서 계산시간이 늘어나고, 이 말은 1만개를 1초에 정렬하면 10만개를 정렬하는 데에는 100초 정도가 필요하다는 이야기이다.

 

버블정렬은 1번째와 2번째 원소를 비교해서 정렬하고, 2번째와 3번째, n-1번째와 n번째를 비교해 정렬 한 뒤, 처음으로 되돌아가 n-2번째와 n-1번째 까지 정렬, ... 결과적으로 최대 n(n-1)/2번 정렬한다. 계산을 하면 1/2(n^2 - n)이지만, 빅오 표기법에 의해서 O(n^2)으로 표현한다.

 

예시 코드

이렇게 좋지 않은 성능과는 대조적으로 구현하기에는 가장 쉬운 정렬 알고리즘 중 하나이다.

void bubbleSort(int arr[], int len){
	for(int i = len - 1; i > 0; i--){
    	for(int j = 0; j < i; j++){
        	if(arr[j] > arr[j+1]){
            	int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

 

 

여담

위의 코드에서 보면 알 수 있듯이 구현하기 매우 쉽다. 하지만, 일반적으로 C++의 stl sort()나, 파이썬 내장 sort() 등 내장 정렬 알고리즘이 사용하기 훨씬 쉬운데다가 성능도 좋기 때문에 실무에서 사용될 일은 없다고 봐도 무방한 알고리즘이다. 그렇다고 하더라도 이론적으로도, 구현하기도 매우 쉽기 때문에 정렬 알고리즘을 처음 배울 때에는 가장 처음 배우는 정렬 알고리즘이라고 할 수 있다.