거품 정렬(Bubble Sort)이란?

거품 정렬(Bubble Sort)은 인접한 두 원소의 대소 관계를 비교하여

작은 값의 원소를 앞으로, 큰 값의 원소를 뒤로 교환하면서 정렬하는 알고리즘이다.

 

자료구조와 알고리즘을 공부해본 사람이라면 알겠지만, 가장 먼저 배우는 정렬 기법이기도 하다.

왜냐하면 이 알고리즘은 구현하기도, 이해하기에도 정말 쉽다는 게 장점이다.

 

하지만 으레 모든 방법이 장점이 있다면, 그에 수반하는 단점도 있는 법.

거품 정렬은 비교와 교환을 반복하면서 시간 복잡도가 O(n^2)으로 비효율적이며

정렬된 데이터에 대해서도 비교를 계속 하므로 최선의 경우에도 O(n^2)의 시간복잡도를 가지게 된다.

아래는 자바로 구현한 거품 정렬이다.

	public static void main(String[] args) {
        int[] arr = {12, 7, 8, 3, 2, 77};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int len = arr.length;

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

위 코드 결과물

 

먼저 배열의 길이를 len 으로 지정한 후,

첫 번째 반복문에서는 정렬할 배열의 모든 원소를 비교하며 반복한다.

두 번째 반복문에서는 인접한 두 원소의 대소를 비교하며,

앞의 값이 뒤의 값보다 크면 두 원소의 위치를 바꿔준다.

 

거품 정렬의 공간복잡도는 O(1)이다.

하지만, 시간복잡도는 최악의 경우 O(n^2)이며,

이는 정렬하려는 배열이 이미 정렬되어 있을 경우에도 적용된다.

따라서, 거품 정렬은 정렬할 데이터가 적은 경우나 이미 정렬된 데이터를 정렬할 때 사용하는 것이 적합하다.

 

거품 정렬의 장점은 구현이 간단하다는 것입니다.

하지만, 정렬 속도가 느리기 때문에 데이터가 많거나 정렬할 데이터가 이미 정렬되어 있을 경우에는 다른 정렬 알고리즘을 사용하는 것이 좋다.