버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

  알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 첫 번째로 정리할 정렬 알고리즘은 버블 정렬입니다.

 

버블 정렬이란?

버블 정렬은 인접한 두 원소를 비교하여 크기 순서대로 정렬하는 알고리즘입니다. 

 

동작 원리

1. 배열을 처음부터 끝까지 순차적으로 비교합니다.
2. 두 원소를 비교하여 만약 순서가 잘못되었다면 두 원소를 교환합니다.
3. 이 과정은 배열 끝까지 진행되고 한 번의 패스가 끝나면 가장 큰 값이 맨 뒤로 이동합니다.
4. 반복적으로 비교하면서 각 패스를 통해 진행됩니다.

예시

[7, 2, 0, 1, 5, 6, 4] 와 같이 정렬되지 않은 배열이 있다고 가정합니다.

 

알고리즘은 배열의 첫 두 숫자 (7, 2)를 비교합니다. 여기서 7 > 2로 정렬되지 않았으므로 두 수의 자리를 바꿉니다.

 

[2, 7, 0, 1, 5, 6, 4] 

 

이를 배열의 처음부터 끝까지 작업하면 됩니다. 즉 0하고 7을 비교하고 자리를 바꾸고 7하고 1하고 비교하고 바꾸는 식으로 작업하면 됩니다.

 

그럼 [2, 0, 1, 5, 6, 4, 7] 1회 정렬이 완료되었습니다. 이를 여러번 반복하면 다음과 같이 진행됩니다.

 

[0, 1,  2, 5, 4, 6, 7] 2회

[0, 1, 2, 4, 5, 6, 7] 3회

[0, 1, 2, 4, 5, 6, 7] 4회

3회와 4회는 아무 변화가 없으니 정렬된 것으로 정의합니다.

 

특징

• 시간 복잡도 : 최악 시간 복잡도는 O(N^2)입니다. 즉 배열의 크기가 커질수록 비효율적입니다.
• 공간 복잡도 : O(1)입니다. 추가적인 메모리 공간을 거의 사용하지 않으며 원본 배열을 직접 수정합니다.
• 코드가 단순하기 때문에 자주 사용됩니다.

 

버블 정렬 구현

public class BubbleSort{
    public static void main(String[] args) {
        int[] arr = new int[] {7, 2, 0, 1, 5, 6, 4};
        System.out.println("정렬 전 배열");
       	for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        
        // 배열을 여러 번 반복
        for(int i = 0; i < arr.length - 1; i++) {
            // 배열의 끝까지 비교하며, 가장 큰 값을 오른쪽으로 밀어냄
            for(int j = 0; j < arr.length - 1; j++) {
                // 인접한 원소를 비교하여 순서가 잘못되었으면 교환
                if(arr[j] > arr[j + 1]) {
                    // 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        
        System.out.println("정렬 후 배열");
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }
}

 

실행 결과

정렬된 모습을 확인할 수 있습니다.