버블 정렬

지난 포스팅에서 제일 작은 값을 선택해서 앞으로 보내는 선택 정렬을 알아 보았다. 이번에는 정렬 알고리즘들중 버블 정렬에 대해서 알아보도록 하자.

 

버블 정렬도 선택 정렬처럼 매우 직관적인 정렬 알고리즘이다.

 

버블정렬은 바로 옆 숫자와 비교해서 작은 숫자를 앞으로 보내주는것을 반복함으로써 정렬을 진행한다.

 

선택정렬은 앞에서부터 정렬이 진행 되는것과는 달리 버블 정렬은 뒤에서부터 정렬이 시작된다. 자리를 바꿔주면서 가장 큰 값이 제일 뒤로 쌓이는 모양이다.

---

버블 정렬의 동작 방법을 살펴보자.

2 10 5 7 8 3 6 1 4 9

1) 2와 10을 비교 했을 때, 2가 작으므로 이동은 일어나지 않는다.

 

2) 10과 5를 비교했을 때, 10이 더 크므로 5와 자리를 바꾼다.

 

2 5 10 7 8 3 6 1 4 9

 

3) 10과 7을 비교했을 때, 10이 더 크므로 7과 자리를 바꾼다.

 

2 5 7 10 8 3 6 1 4 9

 

4) 10과 8을 비교했을 때, 10이 더 크므로 8과 자리를 바꾼다.

 

2 5 7 10 8 3 6 1 4 9

...

 

이렇게 한 사이클이 끝나면 값이 제일 큰 10이 가장 뒤로 정렬되는 모습을 볼 수 있다.

 

2 5 7 8 3 6 1 4 9 10

 

버블 정렬의 과정에서 매 사이클 마다 가장 큰 값이 맨 뒤로 보내지게 된다.

---

다음은 자바로 구현 한 코드이다.

 

/**
 * 가장 비효율적인 정렬 알고리즘
 * O(N^2)
 */
public class 버블정렬 {
    public static void main(String[] args) {
        int i;
        int j;
        int temp = 0;
        int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

        for (i = 0; i < 10; i++) {

            // 정렬이 뒤에서부터 시작된다. 9인 이유는 j+1 인덱스를 접근하기 때문
            for (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 e : arr) {
            System.out.print(e + " ");
        }
    }
}

 

버블 정렬은 정렬 알고리즘 중에서 구현이 가장 간단하지만 가장 비효율적인 알고리즘이다.

 

버블 정렬도 선택 정렬과 동일하게 O(N^2)의 시간복잡도를 갖는다.