다양한 정렬 정리(1) - 버블 정렬

버블 정렬(Bubble Sort)는 선택정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

버블 정렬

버블 정렬은 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식으로 정렬한다. 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 위치까지 살피는 과정을 (n-1)회 반복한다.

위 이미지는 버블 정렬에서 자리를 교환하는 과정을 그림으로 설명한 것이다. 이 과정을 1회 마친 이후에는 배열의 가장 큰 값이 배열의 제일 마지막으로 옮겨지기 때문에 제일 마지막 인덱스는 더이상 참조할 의미가 없다. 그렇기 때문에 경계값을 (n-1)부터 1씩 줄여가며 경계를 정하고 앞에서부터 경계까지 버블정렬을 적용한다.

자바 코드

void bubleSort(int[] arr, int n){
    int temp = 0;
    for(int i = n-1; i >= 0 ; i--){ // i = n-1 ~ 0
        for(int j = 0; j < i-1; j++){ // j = 0 ~ i-1
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

시간 복잡도

시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다. 또한, Bubble Sort는 정렬이 되어있던 되어있지 않던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다.

공간 복잡도

주어진 배열안에서 원소의 교환을 통해 해결하므로, O(n)이다.