[Algorithm] 버블 정렬(Bubble Sort) - C++, Java, Python 구현

그 유명한 버블 정렬에 대해 알아보고 C++, 자바, 파이썬으로 구현해 봅시다.

 

• 자료구조, 알고리즘 시리즈 모아보기

 

버블 정렬

`버블 정렬(bubble sort)`은 선택 정렬처럼 가장 큰 원소를 끝으로 옮기는 작업을 반복하는 알고리즘입니다. 선택 정렬이 큰 값을 콕 찍어서 옯겼다면 버블 정렬은 한쪽 끝에서 긁어 올라가며 더 큰 값만 가지고 올라가는 방식입니다. 이렇게 논리적으로 아래에서부터 수면 위로 올라가는 모습을 컴퓨터 과학에서는 버블링이라고 합니다. DOM트리에서 일어나는 이벤트 버블링도 아래에서 위로 올라가는 의미의 버블링이죠.

- Pseudocode

정렬해야 하는 배열 A[n]이 주어졌을 때 버블 정렬 알고리즘은 다음과 같습니다.

bubbleSort(A[], n){
    for( last ← n downto 2 )
        for( i ← 1 to last-1 )
            if( A[i] > A[i+1] ) A[i] ↔︎ A[i+1];
}

위 수도코드를 보면 if문의 비교는 항상 $n(n-1)\over2$번 실행됩니다. 복잡도는 모든 경우에서 $\Theta(n^2)$로 처음부터 정렬되어 있는 최선의 경우에도 최악인 경우와 수행시간이 큰 차이가 없습니다. 이 부분은 아래와 같이 개선될 수 있습니다.

bubbleSort(A[], n){
    for( last ← n downto 2 ){
        isSorted ← TRUE;
        for( i ← 1 to last-1 ){
            if( A[i] > A[i+1] ){ 
                A[i] ↔︎ A[i+1];
                isSorted ← FALSE;
            }
        }
        if( isSorted ) return;
    }
}

- 시간 복잡도

버블 정렬의 시간 복잡도는 $\Omicron(n^2)$입니다. 모든 경우에서 $\Theta(n^2)$이었지만 남은 배열이 정렬되어 있다면 종료하는 조건을 추가해 최선의 경우 $\Theta(n)$으로 개선할 수 있습니다.

 

구현

- C++

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

void bubble_sort(int arr[], int n) {
    for(int last=n; --last;) {
        bool isSorted = true;
        for(int i=0; i<last; i++) {
            if(arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
                isSorted = false;
            }
        }
        if(isSorted) return;
    }
}

- Java

class Sort {
    public static void bubbleSort(int[] arr){
        for(int last=arr.length-1; last>0; last--){
            boolean isSorted = true;
            for(int i=0; i<last; i++){
                if(arr[i] > arr[i+1]){
                    swap(arr, i, i+1);
                    isSorted = false;
                }
            }
            if(isSorted) return;
        }
    }

    private static void swap(int[] arr, int i, int j){
        if(i==j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

- Python

def bubble_sort(arr):
    n = len(arr)
    isSorted = True
    for last in range(len(arr)-1, 0, -1):
        for i in range(0, last):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                isSorted = False
         
        if isSorted: return

 

재귀

버블 정렬과 선택 정렬은 구조적으로 비슷합니다. 큰 값을 끝으로 옮기는 방법의 차이죠. 버블 정렬을 재귀함수로 구현해 봅시다. 

- C++

void recursive_bubble_sort(int arr[], int n) {
    if(n < 2) return;
    bool isSorted = true;
    for(int i=1; i<n; i++) {
        if(arr[i-1] > arr[i]) {
            swap(arr[i-1], arr[i]);
            isSorted = false;
        }
    }
    if(!isSorted)
        recursive_bubble_sort(arr, n-1);
}

- Python

def bubble_sort(arr, n):
    if n<2: return
    isSorted = True
    for i in range(0, n-1):
        if arr[i] > arr[i+1]:
            arr[i], arr[i+1] = arr[i+1], arr[i]
            isSorted = False
         
    if not isSorted:
        bubble_sort(arr, n-1)

이렇듯 재귀 구조를 갖는 알고리즘에서 반복문은 대체로 재귀함수로 변경될 수 있습니다. 하지만 입력값이 클 때 단순 반복문을 재귀함수로 바꾸게 되면 스택메모리가 낭비되고 스택오버플로우가 발생할 수 있습니다. 지금은 알고리즘과 재귀에 익숙해지는 것이 목표이기 때문에 재귀로 바꿔볼 수 있는 알고리즘은 바꾸면서 연습해 봅시다.