버블정렬(Bubble sort) 알고리즘

버블정렬(Bubble sort)

버블 정렬은 정렬이 이름 처럼 거품이 수면으로 올라오는 것처럼 진행된다고 해서 붙여진 이름 입니다.  

반복적으로 인접한 배열의 크기를 비교해가면서 정렬해나가는 방법으로 매우 쉽게 구현 할 수 있지만 정렬 효율은 좋지 않습니다. 

버블 정렬은 아래와 같은 순서로 진행 됩니다.

1) 배열의 시작부터 인접한 요소 두개를 선택합니다.

2) 요소를 비교해 큰 요소를 뒤로 보냅니다.

3) 모든 배열이 정렬 될 때 까지 위의 과정을 반복합니다.

배열  arr[5]={1, 82, 45, 66, 55} 을 가지고 버블 정렬을 설명 해보겠습니다. 

{ 1, 82, 45, 66, 55 } arr[0] < arr[1] 이므로 교환 하지 않습니다.

{ 1, 82, 45, 66, 55 } -> { 1, 45 ,82, 66, 55 } arr[1] > arr[2] 이므로 교환 합니다.

{ 1, 45, 82, 66, 55 } -> { 1, 45 ,66, 82, 55 } arr[2] > arr[3] 이므로 교환 합니다.

{ 1, 45, 66, 82, 55 } -> { 1, 45, 66, 55, 82 } arr[3] > arr[4] 이므로 교환 합니다.

다시 처음으로 돌아 갑니다.

{ 1, 45, 66, 55, 82 } arr[0] < arr[1] 이므로 교환 하지 않습니다.

{ 1, 45, 66, 55, 82 } arr[1] < arr[2] 이므로 교환 하지 않습니다.

{ 1, 45, 66, 55, 82 } -> { 1, 45, 55, 66, 82 } arr[2] > arr[3] 이므로 교환 합니다.

정렬이 완료 되었지만 알고리즘 입장에선 정렬 여부를 알 수 없으므로 계속해서 진행 합니다.

{ 1, 45, 55, 66, 82 } arr[3] < arr[4] 이므로 교환 하지 않습니다.

                                ...

이처럼 정렬이 완료 된 후에도 계속 정렬 작업을 해야 하므로 버블정렬의 알고리즘은 항상  의 실행 시간을 가집니다.

다음은 자바로 구현한 버블정렬 입니다.

    // 버블정렬 알고리즘은 인접한 두개의 원소를 비교하여 정렬 한다.
    // 코드가 단순 하므로 쉽게 사용 할 수 있다.
    // 시간 복잡도 O(n^2)
    
    // 배열의 요소를 교환 해주는 메소드.
    public void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
 
    public 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] > arr[j + 1]) { 
                    swap(arr, j, j + 1);
                }
            }
 
        }
    }

  버블 정렬 알고리즘은 정렬이 완료 되어도 모든 루프를 수행해야 하지만 내부 루프에서 교환이 발생 하지 않는다면 수행을 중단시킴으로서 성능을 향상 시킬 수 있습니다.

    public void bubbleSort(int[] arr) {
 
        // 배열 교환을 감지할 변수
        boolean swapped;
 
        for (int i = 0; i < arr.length - 1; i++) {
            swapped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    //교환이 발생 한다면 true
                    swapped = true;
                }
            }
            //배열 교환이 발생하지 않았다면 주어진 배열은 이미 정렬이 완료 되어 있음.
            //따라서 루프를 탈출한다.
            if (!swapped)
                break;
        }
    }