Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.

⚙ Process

1. 주어진 배열에서 1회전에 (첫 번째 원소, 두 번째 원소) 비교하여 교환 (두 번째 원소, 세 번째 원소) 비교하여 교환을 반복
2. 1회전 수행이 종료되면 가장 큰 원소는 배열의 맨 뒤에 위치하므로 2회전 정렬에서는 제외된다.

✅ JAVA Code

public int[] bubbleSort(int[] arr){
        for(int i=0; i<arr.length; i++){
            for(int j=1; j<arr.length-i; j++){
                if(arr[j-1] > arr[j]) {
                    int tmp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        return arr;
    }

◻시간복잡도

시간복잡도를 계산하면, (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)

안정 정렬(Stable Sort) 이다.

◻단점

시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.

정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.