거품 정렬 (Bubble Sort)

출처: 위키백과

 

정의

거품 정렬은 1번째와 2번째, 2번째와 3번째, 3번째와 4번째, ... 와 같이 인접한 두 원소를 비교하여 정렬한다.

인접한 두 원소끼리 반복적으로 비교하는 모습이 마치 '거품'과 같다고 하여 거품 정렬이라고 이름이 붙여졌다.

 

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로, 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외할 수 있다.

마찬가지로 2회전을 수행하고 나면 끝에서 두번째 자료까지는 정렬에서 제외된다.

 

설명

[5, 4, 3, 2, 1]

위 배열을 오름차순 정렬해보자.

 

1번째와 2번째를 비교한 후, 2번째 원소가 더 작을 경우 1번째 원소와 교체해 준다.

 

[4, 5, 3, 2, 1]

이번에는 2번째와 3번째를 비교하여 교체해주자.

 

[4, 3, 5, 2, 1]

같은 방식으로 마지막 원소까지 반복한다.

 

[4, 3, 2, 5, 1]

[4, 3, 2, 1, 5]

 

1회전이 끝나고 나면, 배열 내 가장 큰 원소인 5는 가장 뒤로 이동되어 있다.

따라서 가장 마지막 원소는 다음 2회전에서 비교할 필요가 없다.

 

이제 2회전을 시작해보자.

[3, 4, 2, 1, 5]
[3, 2, 4, 1, 5]
[3, 2, 1, 4, 5]

 

2회전이 끝나면 마지막 두 원소, 4번째와 5번째는 정렬이 완료된 것을 볼 수 있다.

같은 방식으로 이어서 정렬해나가면 된다.

 

정렬이 진행되는 순서는 아래와 같다.

// 1회전
5, 4, 3, 2, 1
4, 5, 3, 2, 1
4, 3, 5, 2, 1
4, 3, 2, 5, 1
4, 3, 2, 1, 5

// 2회전
3, 4, 2, 1, 5
3, 2, 4, 1, 5
3, 2, 1, 4, 5

// 3회전
2, 3, 1, 4, 5
2, 1, 3, 4, 5

// 4회전
1, 2, 3, 4, 5

 

복잡도

 

	시간 복잡도	공간 복잡도
Best	N^2	N
Worst	N^2	N
Avg	N^2	N

 

시간 복잡도는 최고, 최악, 평균 모두 N^2이다.

반복을 통한 N회전 마다 N 번의 비교를 통하여 정렬을 하기 때문이다.

 

공간 복잡도는 최고, 최악, 평균 모두 N이다.

매 반복마다 Swap을 통한 메모리 공간을 1회씩 사용하기 때문이다.

 

구현

public class BubbleSort {

    public static void main(String[] args) {
        int[] array = new int[] {5, 2, 3, 4, 1};

        print(array);
        sort(array);
        print(array);
    }

    private static void sort(int[] array) {
        int temp;
        for (int i = array.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                temp = array[j];
                if (array[j] > array[j + 1]) {
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    private static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

        System.out.println("");
    }
}