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

버블정렬(Bubble Sort)

버블정렬은 인접한 두개의 원소를 비교하여 가장 큰 원소가 마지막자리로 오게해서 숫자를 정렬하는 방법입니다.

원소를 두개씩 교환하면서 마지막원소까지 오는 모습이 거품이 물에서 올라오는 것과 비슷하다. 라고 생각하여 버블정렬이라는 이름을 갖게되었답니다..

시간복잡도는 선택정렬과 같이 O(n^2)입니다.

비교횟수가 선택정렬과 똑같기 때문입니다.

1단계 => n 

2단계 => n-1

...

n + (n-1) + (n-2) + ....

// 버블정렬
public void bubbleSort(int[] array) {
    int size = array.length;
     
    for(int i=0; i < size-1; i++) {
        System.out.printf("\n버블 정렬 %d 단계 : ", i + 1);
        for(int j=0; j < size -1 -i; j++) {
            if(array[j] > array[j+1])
                swap(array, j, j+1);
            System.out.printf("\n");
            for(int k=0; k < size; k++) {
                System.out.printf("%4d", array[k]);
            }
        }
    }
}
 
public void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

보시는 것과 같이 오른쪽부터 제일 큰 수가 정렬되고 있습니다. 버블정렬 1단계에서는 가장 처음에 있던 원소 52가 맨끝으로 가면서 1단계가 마무리됩니다.

이런식으로 반복되면서 정렬하는 방법이 버블정렬입니다.

--------------------------- append -----------------------------

위의 코드는 정렬할 리스트가 역순이든, 정렬된 리스트이든 상관없이 for문을 2번 돌기 때문에 O(n^2)의 시간복잡도를 갖고있습니다.

책을보다가 성능이 향상된 버블리스트를 발견했기에 추가합니다.

버블정렬은 구현하기는 간단하지만 비효율적인 알고리즘이라고 합니다.

밑의 코드로 버블정렬을 수행하게되면

최악의 경우 

=> O(n^2)

최선의 경우

=> O(n) 

의 시간복잡도를 갖게됩니다.

최악의 경우에는 위의 코드와 시간복잡도가 같으나, 최선의 경우 시간복잡도가 줄어듭니다.

public void bubbleSort2(int[] array) {
        boolean numbersSwitched;
        do {
            numbersSwitched = false;
            for(int i=0; i<array.length-1; i++) {
                if(array[i+1] < array[i]) {
                    swap(array, i, i+1);
                    numbersSwitched = true;
                }
            }
        }while(numbersSwitched);
    }