2. 버블 정렬(Bubble Sort)

버블 정렬에 대해서 알아보겠습니다.

다음 숫자들을 오름차순으로 정렬하시오.
1  10  5  8  7  6  4  3  2  9

버블 정렬(Bubble Sort)은 인접한 값과 비교하여 더 작은 값을 앞으로 보냅니다. 이 과정을 반복합니다.

알고리즘 중 아이디어는 간단하지만, 가장 비효율적인 알고리즘입니다.

 

소스코드

public class TestMain {
    public static void main(String[] args) {
        int[] array = {1,10,5,8,7,6,4,3,2,9};
        for(int i=0;i<10;i++){
            for(int j=0; j<9-i;j++){
                if(array[j] > array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }

        for(int i:array){
            System.out.print(i+" ");
        }
    }
}

 

연산 횟수는 (N-1) + (N-2) + ...... + 1 = N*(N-1)/2

시간복잡도는 O(N^2) 으로, 선택정렬 알고리즘과 같습니다.

 

이 역시 N값이 커질수록 시간복잡도가 지수적으로 증가합니다. 따라서 비효율적인 알고리즘입니다.

다음 시간에는 삽입정렬에 대해 알아보겠습니다.