버블 정렬(bubble sort)

버블 정렬(bubble sort)

이웃한 두 요소의 대소관계를 비교하여 교환하는 알고리즘.
단순교환정렬이라고도 부른다.
액체안의 공기 방울이 위로 보글보글 올라오는 모습에서 착안했다고 한다.

 

버블 알고리즘에 관하여 3가지 방법으로 구현한 코드와 성능에 대해서 확인해보며, 정렬이 어떻게 진행되는가는 진행되는 과정을 출력으로 확인해보고, 3가지 방법에서 수행되는 교환횟수, 비교횟수를 확인해보자. 

 

동일한 조건 설정을 위하여 {1,3,9,4,7,8,6}의 요소값을 갖는 크기가 7인 배열을 사용한다.

 

아래 출력되는 결과를 통해서도 확인해 볼 수 있듯이 버블정렬은 두 요소값을 비교할 시 값이 같으면 교환이 이루어지지 않는다. 즉, 정렬 전후로 두 요소의 값에 따라 전체적인 위치는 변경되더라도 두 요소 사이에 순서는 변하지 않기에 안정성 있는 정렬 알고리즘이다.

 

출력설명)

+ : 서로 맞닿은 비교대상 요소 간 교환이 이루어져야 할 경우 두 요소 사이 출력
-  : 서로 맞닿은 비교대상 요소 간 교환이 이루어지지 않을 경우 두 요소 사이 출력
패스 : 서로 맞닿은 요소들을 비교해나가는 하나의 사이클

---

Version1)

단순하게 패스마다 비교범위 요소들 전체 비교

    static int change = 0; // 교환 횟수
    static int search = 0; // 비교 횟수
    
    // 교환 시 사용하는 메서드
    static void swap(int[] a , int idx1 , int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
        change++;
    }
    
    // 비교 시 사용하는 메서드
    static void bubbleSort(int[] a , int n){
    	for(int i = 0 ; i < n - 1 ; i++){
           System.out.println("패스"+(i+1));
           for(int j = n - 1 ; j > i ; j--){
               search++;
               for(int k = 0 ; k < n ; ){
                   if(k == j-1){
                       if(a[k] > a[k+1]) System.out.printf("%2d+%d",a[k] ,a[k+1]);
                       else System.out.printf("%2d-%d",a[k] ,a[k+1]);
                       k += 2;
                   }else{
                       System.out.printf("%2d",a[k]);
                       k++;
                   }
               }
               if(a[j - 1] > a[j])
                   swap(a,j - 1 , j);
               System.out.println();
           }
       }
    }
    
    //메인 메서드
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.println("버블 정렬");
        System.out.print("요솟수 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for(int i = 0 ; i < nx; i++){
            System.out.print("x["+i+"]: ");
            x[i] = stdIn.nextInt();
        }

        bubbleSort(x,nx);
        System.out.println("\n오름차순으로 정렬했습니다.");
        for(int i = 0 ; i < nx ; i++)
            System.out.println("x["+i+"]=" + x[i]);

        System.out.println("change = " + change);
        System.out.println("search = " + search);
    }

아래결과와 같이 총 21회 비교와 6회 교환이 이루어진다. 각 패스마다 + / - 부분을 확인해보면 비교하는 범위가 어떻게 변화하는지 알 수 있다. 간단하게 i값이 패스를 다 돌면 증가하는데 현재 i값은 앞에서부터 얼마나 정렬이 되었는지를 알 수 있는 부분이기도 하다. 

Version1 버블정렬  출력결과

 

---

Version2)

패스마다 비교 시 중간에 정렬이 완료되었다면 뒷 부분을 체크하지 않고 정렬완료

    static void bubbleSort(int[] a , int n){
    	for(int i = 0 ; i < n - 1 ; i++){
            int exchg = 0; // 패스마다 교환횟수 체크
            System.out.println("패스"+ (i+1));
            for(int j = n - 1 ;  j > i ; j--){
                search++;
                for(int k = 0 ; k < n ; ){
                    if(k == j -1 ){
                        if(a[k] > a[k+1]) System.out.printf("%2d+%d",a[k],a[k+1]);
                        else System.out.printf("%2d-%d",a[k],a[k+1]);
                        k += 2;
                    }else{
                        System.out.printf("%2d",a[k]);
                        k++;
                    }
                }
                if(a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                    exchg++;
                }
                System.out.println();
            }
            if(exchg == 0) break;
        }
    }

위에 결과와 비교해서 패스 4에서 실질적으로 모든 정렬이 완료되었다. 그렇기에 패스5에서 모든 요소가 정렬된 것이 확인되었으며, 이는 다시말해 교환이 더 이상 발생하지 않았기에 exchg는 값이 0이되고 정렬은 마무리가 된다. 여기서 확인해 볼 수 있는 부분은 교환은 동일한 횟수로 발생하지만 비교는 줄어들게된다. 이 부분은 초기 배열에 상태에 의존한다. 극단적 예로 초기 배열이 정렬이 잘 되어 있을 수록 version1은 끝까지 패스마다 수행되지만 version2의 경우는 빠른시간에 정렬이 끝나고 더 이상 동작을 수행하지 않게된다.

Version2 버블정렬  출력결과

---

Version3)

앞 부분에서 이미 정렬이 완료될 시 앞 부분은 제외하고 정렬 수행

    static void bubbleSort(int[] a , int n) {
        int k = 0; // 앞 부분 정렬 위치 위함.
        int pass = 1; // 현재 패스출력 위함.
        while (k < n-1){
            int last = n - 1;
            System.out.println("패스"+pass++);
            for(int j = n - 1 ; j > k ; j--){
                search++;
                for(int c = 0 ; c < n ; ){
                    if(c == j -1 ){
                        if(a[c] > a[c+1]) System.out.printf("%2d+%d",a[c],a[c+1]);
                        else System.out.printf("%2d-%d",a[c],a[c+1]);
                        c += 2;
                    }else{
                        System.out.printf("%2d",a[c]);
                        c++;
                    }
                }
                if(a[j-1] > a[j]){
                    swap(a,j-1,j);
                    last = j;
                }
                System.out.println();
            }
            k = last;
        }
    }

아래 출력결과에서도 확인 할 수 있듯이 교환횟수는 동일하나 비교횟수가 확실히 줄어든 것을 볼 수 있다. 다음으로 각 패스마다 비교하는 범위를 보면 앞 부분에서 이미 정렬이 이루어지지 않았을 경우 Version2에서는 비교가 이루어지지만 Version3 같은 경우는 마지막 정렬이 이루어진 곳 이후부터 비교범위가 설정된다. 이를 잠시 살펴보면 각 패스마다 가장 뒤 요소부터 시작해서 이웃 요소와 비교를 하게 된다. 즉 현재 요소와 그 앞 부분 요소 간 비교가 이루어진다. 이때 마지막으로 비교를 통해서 앞 요소와 교환이 이루어 진 곳을 확인하면 그 앞쪽은 모두 정렬이 된 상태가 된다. 이렇게 반복을 통해서 정렬된 위치를 변경해나가면 최종적으로 더 이상 교환이 이루어지지 않는 시점에서 조건문을 통한 위치저장이 이루어지지 않기에 while문 초기값으로 설정한 k = n-1이므로 while문을 빠져나온다.

Version3 버블정렬  출력결과