버블 정렬(Bubble Sort)

버블 정렬이란?

버블 정렬은 요소의 앞뒤를 비교해가면서 정렬하는 정렬 알고리즘입니다. 전체를 한 번 돌때마다 정렬된 데이터가 1개씩 증가하게 됩니다. 그리고 버블 정렬의 가장 큰 특징이 있는데, 이미 정렬된 데이터의 경우 시간복잡도가 O(n)입니다.

이것이 중요한 이유는 대개의 데이터는 정렬이 되어있을 수도 있고, 정렬이 되지 않은 상태로 들어올 수 있는데 이 때, 선택정렬을 수행한다면, 항상 O(n2)의 시간이 소요되게 됩니다.

물론 버블 정렬의 시간 복잡도는 O(n2)이기 때문에 실전에선 사용되지 않습니다.

다만 선택 정렬과 마찬가지로, 여러 접근방법을 제시해주기 때문에 배우는 것이라고 생각하면 좋을 것 같습니다.

class BubbleSort {
    public void sort(int[] arr) {
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) { // 마지막 요소는 비교할 필요 없음.
            for (int j = 0; j < length - j - 1; j++) { // 이미 정렬된 요소를 배제하기 위한 튜닝.
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

요약

버블 정렬의 경우도 학습용 정렬이지만, 버블 정렬의 특성인 이미 정렬된 요소의 경우 O(n)의 시간이 소요된다는 사실은 알아두어야 합니다. 의미는 없지만, 선택 정렬과 버블 정렬의 평균적인 속도 차이는 선택 정렬이 두 배 정도 빠르다는 사실도 알아두면 좋습니다. 참고

그 이유는 다를 경우 생기는 swap의 시간이 있기 때문입니다. (버블정렬은 바꾸는 경우가 굉장히 빈번합니다.)