[CS50] 알고리즘 - 버블 정렬

정렬되지 않은 배열을 탐색하는 것보다 정렬 후 탐색하는 것이 더 효율적이다.

정렬 알고리즘은 여러 가지가 있으며 각각 실행 시간이 다르다. 그중 버블 정렬에 대해 배워보자.

 

버블 정렬(Bubble Sort)은 두 개의 인접한 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다.

 

단 두 개의 요소만 정렬하는 좁은 범위의 정렬에 집중한다. 이 접근법은 간단하지만 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있다.

 

동작 원리

8개의 숫자가 임의의 순서로 나열되어 있다.

6 3 8 5 2 7 4 1

 

오름차순으로 정렬해보자.

1. 가장 앞의 6과 3을 비교해 순서를 바꾼다.

 

2. 6과 8은 순서가 맞으므로 그대로 둔다. 8과 5를 비교해 순서를 바꾼다.

 

3. 이 과정을 끝까지 수행하면 다음과 같다.

 

4. 아직 완전히 정렬되지 않았으므로 다시 처음부터 반복한다.

 

최종 결과:

1 2 3 4 5 6 7 8

마치 거품이 터지며 위로 올라오듯 정렬되는 방식이라 '버블 정렬'이라고 한다.

 

의사 코드:

Repeat n-1 times
    For i from 0 to n-2
        If i'th and i+1'th elements out of order
            Swap them

 

시간 복잡도

중첩 루프를 사용하며, n개의 값이 주어졌을 때:

• 외부 루프: n-1번
• 내부 루프: n-2번
• 총 비교 횟수: (n-1) × (n-2) = n² - 3n + 2

가장 큰 항은 n²이므로:

• 상한 (최악의 경우): O(n²)
• 하한 (최선의 경우): Ω(n²)

정렬 여부와 관계없이 모든 비교를 수행하므로 최선의 경우에도 Ω(n²)이다.

 

연습 문제

Q. 버블 정렬이 효율적인 경우는 언제이고, 비효율적인 경우는 언제일까?
효율적인 경우:

1. 데이터 양이 적을 때
   • 간단한 구현으로 충분히 빠름
   • 코드 복잡도가 낮아 이해하기 쉬움
2. 거의 정렬된 데이터
   • 최적화된 버블 정렬(조기 종료)을 사용하면 O(n)까지 가능
   • 소량의 교환만 필요

비효율적인 경우:

1. 데이터 양이 많을 때
   • O(n²) 시간 복잡도로 인해 매우 느림
   • 병합 정렬(O(n log n)) 등이 더 효율적
2. 역순으로 정렬된 데이터
   • 최대한의 교환이 필요
   • 모든 요소를 끝까지 이동시켜야 함

 

결론
- 작은 데이터셋이나 교육용으로 적합
- 실무에서는 퀵 정렬, 병합 정렬 등을 사용