버블소트는 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.

인접한 2개의 원소를 비교해 크기가 순서대로 되어있지 않으면 서로 교환합니다. 선택정렬과 기본 개념이 유서하죠.

로직

• 1단계에서 첫번째 원소와 두번째 원소를, 두번째 원소와 세번째원소를, 세번째 원소와 네번째 원소를 ... 이런식으로 마지막 -1번째 원소와 마지막원소를 비교하여 조건에 맞지않을 경우 서로 교환합니다.
• 1단계를 수행하고나면 가장 큰 원소가 맨 뒤로 이동하므로 2단계에서는 맨끝에 있는 원소는 정렬에서 제외되고, 2단계를 수행하고나면 두번째 원소까지는 정렬에서 제외됩니다. 이렇게 단계를 수행해갈수록 정렬에서 제외되는 데이터가 늘어나게됩니다.

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

            System.out.print((i + 1) + "단계 : ");
            print(arr);
        }
    }

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

// 단계별 결과.
1단계 : 6 2 4 3 7 1 9 
2단계 : 2 4 3 6 1 7 9 
3단계 : 2 3 4 1 6 7 9 
4단계 : 2 3 1 4 6 7 9 
5단계 : 2 1 3 4 6 7 9 
6단계 : 1 2 3 4 6 7 9 
7단계 : 1 2 3 4 6 7 9

시간 복잡도

(n-1) + n-2 + n-3 + ... +2 + 1이므로 n(n-1)/2로 insertion sort와 동일합니다. 즉 O(N^2)입니다.

정렬이 되어있건 말건 상관하지 않기에 최악, 최선, 평균 모두 O(N^2)의 시간복잡도를 가집니다.

공간복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)입니다.

장점

• 구현이 간단하고 소스코드가 직관적입니다.
• 뒤의 원소부터 정렬되기 때문에 삽입정렬과 달리 안정정렬입니다.

단점

• 시간복잡도가 항상 O(N^2)으로 비효율적입니다.
• 정렬속도가 다른 정렬에 비해 느립니다.
• 교환횟수가 많고, 역순배열을 정렬할 경우 가장 느리게 동작합니다.