[Algorithm] 거품 정렬 (Bubble Sort)

거품 정렬 (Bubble Sort)

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘
끝에서 부터 정렬이 이루어진다.

 

public class p02_bubbleSort {
    // 오름 차순
    public static int[] solution(int n, int[] arr){
        for(int i = 0; i < n-1; i++){
            for(int j = 0; j < n-i-1; j++){
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }

    // 내림 차순
    public static int[] solution2(int n, int[] arr){
        for(int i = 0; i < n-1; i++){
            for(int j = 0; j < n-i-1; j++){
                if(arr[j] < arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        for(int x: solution(n, arr))
            System.out.print(x+" ");
    }
}

시간복잡도

(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2  이므로 O(n^2) 이다.

Bubble Sort는 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다. 

 

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.

 

장점

• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. → 제자리 정렬( in-place sorting )
• 안정정렬 (중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리) 이다. 

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)이다.
• 정렬 돼있지 않은 원소가 정렬 됐을 때의 자리로 가기 위해서, 교환 연산이 많이 일어나게 된다.

 

---

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview