거품 정렬(Bubble Sort).md

거품 정렬(Bubble Sort)

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
• 인접한 2개의 원소를 비교해 크기가 순서대로 되어 있지 않으면 서로 교환한다.
• 선택 정렬과 기본 개념이 유사하다.

로직

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, ... 이런 식으로 마지막 - 1 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

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 

• 첫 번째 for문은 제외될 원소의 갯수를 의미한다. 1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜준다. 2회전이 끝나면 배열의 마지막 두 위치에는 큰 원소 2개가 정렬된 상태로 위치할 것이기 때문에 2개를 제외하면 된다.
• 두 번째 for문은 원소를 비교할 index를 뽑는 for문이다. j는 0부터 arr.lenght-i-1까지 증가한다. 현재 원소와 다음 원소를 가리키기 때문에 0부터 시작한다.
• 세 번째 for문은 가리키고 있는 두 원소를 비교한다. 오름차순 정렬이므로 현재 원소가 다음 원소보다 크다면 다음 원소가 앞으로 오고 현재 원소가 뒤로 가야 하므로 서로 자리를 교환한다.

시간 복잡도

(n-1)+(n-2)+(n-3)+ ... +2+1 => n(n-1)/2이므로, O(N^2)이다.

버블 정렬은 정렬이 되어있건, 안되어있건 2개의 원소를 비교하기 때문에 최악의 경우, 최선의 경우, 평균의 경우 모두 시간 복잡도가 O(N^2)으로 동일하다.

공간 복잡도

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

장점

• 구현이 간단하고 소스코드가 직관적이다.
• 이미 정렬된 데이터를 정렬할 때, 가장 빠르다.
• 정렬하고자 하는 배열 안에서 정렬하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
• 안정 정렬이다.

단점

• 시간 복잡도가 최악, 최선, 평균 모두 O(N^2)이므로 비효율적이다.
• 다른 정렬에 비해 정렬 속도가 느리다.
• 교환 횟수가 많다.
• 역순배열을 정렬할 때, 가장 느리다.