[Algorithm] Bubble Sort

버블 정렬은 사실상 거의 쓰이지 않는 정렬이지만, 가장 기초적인 정렬 알고리즘이다.

삽입정렬이나 선택정렬과 같은 O(N2) 제곱 의 시간복잡도를 갖는다 하더라도 거품정렬의 교환횟수가 평균적으로 더 많기 때문에 실질적으로는 삽입, 선택 정렬보다 더 많은 시간이 걸리기 때문이다.

 

결론부터 말하자면  swap 여부를 판단할 수 있다면 O(N), 구분할 수 없다면 0(N2)이다. 

 

아래를 예시를 살펴보자 

결국 저기서 중요한건 배열 요소의 개수는 6개이고, 정렬을 위한 Round는 5회였다.

Round별 비교를 하는 횟수는 배열 요소의 개수(길이) - Round 이다.

위의 각 라운드를 보면 값 교환과정이 상당히 많다, 그렇기 때문에 효율성이 떨어져 구현하기 쉽지만

잘 쓰이지 않는다.

 

package DS.sort;

class BubbleSort{
    public void sort(int a[]){
        sort(a, a.length);
    }
    public void sort(int a[], int length){
        //round는 배열의 크기 -1만큼 진행됨
        for(int i = 1; i<length ; i++){

            //round별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교
            for(int j=0;j<length-i;j++){
                /**
                 * 현재 원소가 다음 원소보다 클 경우
                 * 서로 원소의 위치를 swap
                 * */
                if(a[j]>a[j+1]){
                    swap(a,j,j+1);
                }
            }
        }
    }
    public void swap(int a[],int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

public class BubbleSortTest {

    public static void main(String[] args) {
        BubbleSort bubbleSort = new BubbleSort();
        int[] arr = new int[] {45,3,26,55,6,20};

        bubbleSort.sort(arr);

        for (int a:
             arr) {
            System.out.print(a + " ");
        }
    }
}

 

버블정렬의 시간복잡도는 O(N2)이다. 이를 O(N)으로 바꿀수 있을까?

각 라운드에서 비교수행시 원소가 교환되지 않았다면, 스왑이 발생되지 않았다면 이미 정렬이 되었다는 의미로

파악해서 정렬을 종료하면 되는 방법이 있다.

 

package DS.sort;

class BubbleSort{

    boolean isSwapped;

    public void sort(int a[]){
        sort(a, a.length);
    }
    public void sort(int a[], int length){
        //round는 배열의 크기 -1만큼 진행됨
        for(int i = 1; i<length ; i++){

            isSwapped = false;

            //round별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교
            for(int j=0;j<length-i;j++){
                /**
                 * 현재 원소가 다음 원소보다 클 경우
                 * 서로 원소의 위치를 swap
                 * */
                if(a[j]>a[j+1]){
                    swap(a,j,j+1);
                    isSwapped = true;
                }
            }
            
            //스왑된적이 없다면 반복문 종료
            if(!isSwapped){
                break; 
            }
        }
    }
    public void swap(int a[],int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

public class BubbleSortTest {

    public static void main(String[] args) {
        BubbleSort bubbleSort = new BubbleSort();
        int[] arr = new int[] {1,2,3,4,5};

        bubbleSort.sort(arr);

        for (int a:
             arr) {
            System.out.print(a + " ");
        }
    }
}