[알고리즘] 버블 정렬 (Bubble Sort)

목차

버블 정렬이란?

버블 정렬이란 옆에 있는 값과 비교해서 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법이다. 만약에 내림차순으로 정렬을 한다고 하면 옆에 있는 값과 비교해서 더 큰 값을 앞으로 보내면 된다. 

 

우선 예시를 하나 살펴보겠다. 다음과 같은 배열을 오름차순으로 정렬한다고 가정하겠다.

 

 

우선 첫 번째와 두 번째 숫자, 즉 4와 2를 비교한다.

 

 

2가 4보다 더 작으니 더 작은 숫자인 2를 앞으로 보낸다.

 

 

그다음에는 두 번째와 세 번째 숫자, 즉 4와 1을 비교한다.

 

 

비교하고 더 작은 1을 앞으로 보낸다.

 

 

4와 5를 비교했을 때 4가 더 작으니 건너뛴다. 이 과정을 끝까지 반복하면 다음과 같다.

 

 

이 예시에서 알 수 있듯이 더 큰 숫자가 계속 뒤로 밀려나고 마지막에는 가장 큰 숫자가 맨 뒤로 밀려난다. 즉, 각 사이클마다 가장 큰 숫자가 뒤로 밀려나는 것이다. 정렬을 다 하면 다음과 같다.

 

 

 

소스 코드

 

//버블 정렬을 이용해서 오름차순으로 정렬하기
static void bubbleSort() {
    //정렬할 배열
    int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    int temp;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 9 - i; j++) {
            //현재 숫자가 다음 숫자보다 더 클 때
            if (arr[j] > arr[j + 1]) {
                //서로 값 바꾸기
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

    //정렬한 배열 출력하기
    for (int i = 0; i < 10; i++) {
        System.out.println(arr[i]);
    }
}

 

버블 정렬에서는 단순히 두 숫자를 비교해서 더 작은 숫자를 앞으로 보낸다. 이 과정을 반복하다 보면 각 사이클마다 가장 큰 값이 맨 뒤로 보내지게 된다. 따라서 안에 있는 for-loop이 j < 9 - i까지 하는 이유는 여기에 있다. 항상 가장 큰 값은 맨 뒤로 보내지기 때문에 범위를 하나씩 줄이는 것이다.

 

 

시간 복잡도

버블 정렬의 시간 복잡도는 O(N^2)이다.

 

하지만 선택 정렬과 비교했을 때 실제로는 선택 정렬보다 더 느리다. 이 이유는 버블 정렬에서는 당장 옆에 있는 숫자와 비교해서 계속 자리를 바꿔준다. 하지만, 선택 정렬은 가장 작은 숫자를 골라서 맨 마지막에만 자리를 바꿔준다. 따라서, 버블 정렬이 실제로는 수행 시간이 더 느리다고 할 수 있다.

 

버블 정렬은 구현이 간단하다는 장점이 있지만 정렬 알고리즘 중에서 가장 비효율적이다는 단점이 있다. 비효율적이어서 실제로는 거의 사용되지 않는다고 한다.