거품 정렬 (Bubble Sort)

1. 개념 설명

(1) 거품 정렬은 서로 인접한 두 원소의 대소를 비교하고 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

 

 

 

 

2. 과정

by 위키피디아

 

- 실제로 수행되는 과정이며, 배열 0 인덱스부터 순차적으로 비교한다.

 

by 위키피디아

 

 

 

 

 

3. 코드

public class BubbleSort {
   static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
   static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        int[] A = { 7, 2, 8, 10, 1 };
        
        for(int i=0; i<A.length-1; i++) {
            for(int j=0; j<A.length-1-i; j++) {
                if(A[j]>A[j+1]) {
                    int tmp=A[j];
                    A[j]=A[j+1];
                    A[j+1]=tmp;
                }
            }
        }
        for(int i : A) {
            System.out.print(i+" ");
        }
    }
}

 

 

 

 

4. 시간 복잡도

(1) 수행 횟수를 보면 (n-1) + (n-2) + ... + 2 + 1 --> n(n-1)/2가 나오게 된다.

 

(2) 그러므로, 버블 정렬에 시간 복잡도는 O(n²)이다.

( 시간 복잡도가 상당히 느리지만, 코드가 단순하므로 자주 사용된다고 한다. )

 

 

 

 

5. 공간 복잡도

(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(n)이다.

 

 

 

 

6. 장점

(1) 코드가 매우 단순하며 직관적이다.

 

(2) 주어진 배열 안에서 정렬되기 때문에 다른 메모리 공간이 필요하지 않다.

( *제자리 정렬 (in-place sorting) )

 

(3) 안정 정렬이다.

 

 

 

 

7. 단점

(1) 시간 복잡도가 최선, 평균, 최악 모두 O(n²)이므로, 시간이 오래 걸리기 때문에 굉장히 비효율적이다.

 

(2) Swap이 많이 일어난다.