거품정렬(Bubble Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI

알고리즘 개념

• 항목의 키 값을 풍선에 비유한 것으로 값이 클수록 더 높이 올라가도록 한다.
• 가장 큰 값의 키가 오른쪽 끝으로 이동하고, 그다음 큰 값이 그 옆으로 이동하는 과정을 반복한다.

과정

1. 첫번째 수와 두 번째 수를 비교해서 큰 수가 오른쪽에 위치하게 교체한다.
2. 두 번째 수와 세 번째 수를 비교해서 큰 수가 오른쪽에 위치하게 교체한다.
3. 가장 오른쪽에 도달할 때까지 1,2번을 반복한다
4. 오른쪽 끝에 최대값이 도달하였음으로 이 수를 제외하고 나머지 수에 대해서 수가 1개가 남을 때까지 1~3번 과정을 반복한다.

코드

int temp;
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - 1; j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }

장점

• 구현이 간단하고 단순하다.

단점

• 성능이 좋지 않다(O(n^2))

시간 복잡도

• (n-1) + (n-2) +.... + 2 + 1 => n(n-1)/2
• 최선, 평균, 최악 모두 O(n^2)

공간복잡도

• O(n)
• 별도의 메모리 공간이 필요하지 않은 제자리 정렬(in-place sorting)

---

정렬 알고리즘 시간 복잡도 정리

정렬	최선	평균	최악
선택정렬(Selection Sort)	O(n^2)	O(n^2)	O(n^2)
거품정렬(Bubble Sort)	O(n^2)	O(n^2)	O(n^2)
삽입정렬(Insertion Sort)	O(n)	O(n^2)	O(n^2)
퀵정렬(Quick Sort)	O(nlogn)	O(nlogn)	O(n^2)
병합정렬(Merge Sort)	O(nlogn)	O(nlogn)	O(nlogn)
힙정렬(Heap Sort)	O(nlogn)	O(nlogn)	O(nlogn)