버블(거품)정렬(Bubble Sort)

버블정렬은 데이터의 모든 원소를 하나씩  무식하게 비교해가면서 정렬하는 기법(부르트포스(Brute Force) 의 한 종류) 으로 정렬시 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블(거품)정렬이라고 부른다.  

알고리즘을 살펴보기 전에 VisuAlgo 에서 어떤 방식으로 정렬되는지 시뮬레이션 해보자.

 

버블정렬은 모든 원소를 하나씩 비교해서 원하는 정렬 규칙에 맞게 두 원소를 서로 swap 하는 과정을 거친다.

쉽게 설명하기위해 정렬되지 않은 배열 numbers 가 아래처럼 있다고 할때 오름차순으로 버블정렬 하때 순서는 아래와 같다.

(아래 이미지들의 출처는 튜토리얼 포인트 입니다.)

출처 : 튜토리얼포인트

버블소트는 처음 2개의 원소(numbers[0], numbers[1])를 비교한다.  비교해서 만약 첫번째 원소가 두번째 원소보다 크다면 서로 위치를 swap(교환) 한해야 다. 하지만 14는 33보다 작으므로 swap 할 필요가 없다.

이제 numbers[1] = 33과 numbers[2] = 27를 비교한다. 

33은 22보다 크기 때문에 서로 swap 한다.

이제 numbers[2] = 33과 numbers[3] = 35 를 비교한다. (swap 하기전 numbers[2] 는 27이였으나 swap 후 33으로 교환되어 있는 상태이다.)

33은 35보다 작으므로 swap 할 필요가 없다. 따라서 다음 원소 numbers[3] = 35과 numbers[4] = 10 을 비교한다.

 

35는 10보다 크기 때문에 서로 교환한다.

첫번째 이터레이션이 모두 마치면 최종적으로 14, 27, 33, 10, 35로 되어 있고 이터레이션이 끝나면 하나씩(여기서는 35가 맨 끝으로 이동됨) 정렬된다.  위와 같은 이터레이션을 데이터의 개수만큼 반복하면 최종적으로 오름차순 정렬이 완료된다.

 자 이제 버블정렬 알고리즘을 코드로 구현해 보자.

 

public class Main {
 
    public static void main(String[] args) {
        int[] a = {254,3,213,64,75,56,4,324,65,78,9,5,76,3410,8,342,76};
        bubbleSort(a);
 
        for(int i = 0 ; i < a.length ; i ++) {
            System.out.println(a[i]);
        }
 
    }
 
    private static void bubbleSort(int[] a) {
        // 원소의 개수만큼 루프를 돈다.
        for(int i = 0 ; i < a.length ; i++) {
            for(int j = 0; j < a.length -1 - i ; j++) {
                // 만약 j 원소가 j+1 보다 크다면 오름차순정렬을 위해 두 원소를 서로 swap 한다.
                if(a[j] > a[j+1]) {
                    swap(a, j, j+1);
                }
            }
        }
 
    }
 
    // 두 원소를 서로 swap(교환한다)
    private  static   void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
 
}
 
 

버블정렬은 내부적으로 2중 for-loop 가 필요하기 때문에 시간복잡도는 O(n^2) 이 된다. 

시간 복잡도로 보면 성능이 매우 나빠 정렬이 필요한 데이터가 큰 경우 사용하면 안된다. 

 

연습문제

• 백준 2941 - 나무조각

레퍼런스

• TutorialPoint - bubble sort 
• Wikipedia - 거품정렬
• VisuAlgo