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

버블 정렬

코드 설계

• 배열의 왼쪽에서 오른쪽으로 여러번 스캔
• 스캔 시 인접한 배열의 값과 비교하여 인덱스가 큰 배열의 요소 값보다 인덱스 값이 작은 배열의 요소의 값이 클 경우 위치를 바꾼다.

* 2, 7, 4, 1, 5, 3
1차 -> 2, 4, 1, 5, 3, 7
2차 -> 2, 1, 4, 3, 5, 7
3차 -> 1, 2, 3, 4, 5, 7

// pseudo-code
BubbleSort(A, n) {
    for k <- 1 to n-1 {
        for i <- 0 to n-2 {
            if( A[i] > A[i+1]) {
                swap(A[i], A[i+1])
            }
        }
    }
}

// pseudo-code
BubbleSort(A, n) {
    for k <- 1 to n-1 {
        flag <- 0
        for i <- 0 to n-k {
            if( A[i] > A[i+1]) {
                swap(A[i], A[i+1])
                flag <- 1
            }
        }
        if (flag == 0) break
    }
}

코드 구현

public int[] bubbleSort(int[] A, int n) {
    int[] ret;

    for(int k = 1 ; k < n ; k++) { // 1 ~ n - 1 까지 
        for(int i = 0 ; i < n - 1 ; i++) { // 0부터 n - 2 까지
            if(A[i] > A[i+1]) {

                int tmp = A[i];
                A[i] = A[i+1];
                A[i+1] = tmp;
                // 과정 출력
            }
        }
    }

    ret = A;
    return ret;
}

• 과정

0:     2    7    4    1    5    3    
1:     2    4    7    1    5    3    
2:     2    4    1    7    5    3    
3:     2    4    1    5    7    3    
4:     2    4    1    5    3    7    

0:     2    4    1    5    3    7    
1:     2    1    4    5    3    7    
2:     2    1    4    5    3    7    
3:     2    1    4    3    5    7    
4:     2    1    4    3    5    7    

0:     1    2    4    3    5    7    
1:     1    2    4    3    5    7    
2:     1    2    3    4    5    7    
3:     1    2    3    4    5    7    
4:     1    2    3    4    5    7    

0:     1    2    3    4    5    7    
1:     1    2    3    4    5    7    
2:     1    2    3    4    5    7    
3:     1    2    3    4    5    7    
4:     1    2    3    4    5    7    

0:     1    2    3    4    5    7    
1:     1    2    3    4    5    7    
2:     1    2    3    4    5    7    
3:     1    2    3    4    5    7    
4:     1    2    3    4    5    7    

• swap이 없는 경우 loop에서 벗어나는 flag 설정

    public int[] bubbleSort1(int[] A, int n) {
        int[] ret;
        boolean flag = false;

        for(int k = 1 ; k < n ; k++) { // 1 ~ n - 1 까지 
            flag = false;

            for(int i = 0 ; i < n - k ; i++) { // 0부터 n - k 까지
                if(A[i] > A[i+1]) {

                    int tmp = A[i];
                    A[i] = A[i+1];
                    A[i+1] = tmp;

                    flag = true;
                    // 과정 출력
                }
            }
            if(!flag) break;

        }

        ret = A;
        return ret;
    }

• 과정

1:     2    4    7    1    5    3    
2:     2    4    1    7    5    3    
3:     2    4    1    5    7    3    
4:     2    4    1    5    3    7    

1:     2    1    4    5    3    7    
3:     2    1    4    3    5    7    

0:     1    2    4    3    5    7    
2:     1    2    3    4    5    7

• 결과 확인 테스트

    int[] A = {2, 7, 4, 1, 5, 3};
    int n = A.length;

    @Test
    public void testBubble() {
        int[] except = {1, 2, 3, 4, 5, 7};
        assertThat(bubbleSort(A, n), is(except));
    }

    @Test
    public void testBubble1() {
        int[] except = {1, 2, 3, 4, 5, 7};
        assertThat(bubbleSort1(A, n), is(except));
    }

분석

• 복잡도 분석
  • Bast-Case O(n)
  • Average-Case O(n^2)
  • Worst-Case O(n^2)
• 선택 정렬만큼 우수하지만 마찬가지로 느린 정렬 방식