[정렬] Bubble Sort (버블정렬) - Java

1. 버블정렬이란?

인접한 두 요소를 비교하여 정렬하는 간단한 알고리즘이다. 왜 버블정렬일까? 가장 큰 요소가 배열의 마지막 위치로 버블처럼 떠오른다고 하여 '버블정렬' 이라는 이름으로 유래됨.

 

2. 시간복잡도

각 정렬 과정마다 다시 한번 배열을 순회하여 인접한 두 요소를 비교해야 하므로 O(N^2) 의 시간복잡도를 가진다.

 

3. 핵심이론

1) 배열 사이즈가 N이라고 가정한다.

2) 버블 정렬은 총 (N - 1)번의 과정을 거친다.

3) 각 정렬 과정마다 맨 끝 요소는 정렬이 된 상태이므로 (N - i - 1)번 순회한다.

4) 이전 요소가 다음 요소보다 크면 swap 진행

5) 위 과정 반복

 

4. 예시

아래 N이라는 배열이 있다고 가정하자.

5

4

3

2

1

1) 첫번째 순회

4

5

3

2

1

4

3

5

2

1

4

3

2

5

1

4

3

2

1

5 (가장 큰 요소가 배열의 끝에 옴)

첫번째 순회는 총 4번 (N - 0 - 1) 번 진행한다.

 

2) 두번째 순회

3

4

2

1

5

3

2

4

1

5

3

2

1

4 (그 다음 큰 요소가 배열의 끝에 옴)

5 (이미 정렬 완료)

두번째 순회는 총 3번 (N - 1 - 1)번 순회한다.

 

3) 세번째 순회

2

3

1

4

5

2

1

3 (그 다음 큰 요소가 배열의 끝에 옴)

4 (이미 정렬 완료)

5 (이미 정렬 완료)

세번째 순회는 총 2번 (N - 2 - 1)번 순회한다.

 

4) 네번째 순회

1

2 (그 다음 큰 요소가 배열의 끝에 옴)

3 (이미 정렬 완료)

4 (이미 정렬 완료)

5 (이미 정렬 완료)

총 네 번 (N - 1번)의 정렬 과정의 (N - i - 1)번의 비교 과정으로 버블정렬은 종료된다.

 

예시 코드

public class Main {
    public static void bubbleSort(int[] arr){
        // 버블정렬 수행
        for(int i = 0; i < arr.length - 1; i++){
            for(int j = 0; j < arr.length - i - 1; j++){
                if(arr[j + 1] < arr[j]){
                    swap(arr, j + 1, j);
                }
            }
        }
    }
	
    // swap 함수
    public static void swap(int[] arr, int t1, int t2){
        int temp = arr[t1];
        arr[t1] = arr[t2];
        arr[t2] = temp;
    }

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

        bubbleSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

출력 결과 : 1 2 3 4 5