버블 정렬 (Bubble Sort)

버블 정렬은 기본적인 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 순서에 맞지 않으면 두 원소의 위치를 교환하는 방식으로 진행한다.

버블 정렬은 구현은 간단하지만 시간복잡도가 O(n²)으로 효율성이 다른 알고리즘에 비해 효율성이 낮아 실제로는 거의 사용되지 않는다.

알고리즘 원리

버블 정렬 알고리즘의 원리부터 알아보고 시작해보자.

원리는 아래와 같다.

과정을 보면 눈치챘다시피, 각 사이클마다 가장 큰 원소가 맨 뒤로 버블처럼 떠오르듯 이동하기 때문에 버블 정렬이라고 부른다. 아래에 있는 진행 예시를 보면서 실제 진행 과정을 살펴보도록 하자.

알고리즘 진행 예시

배열 [64, 12, 33, 72, 32]을 버블 정렬로 정렬하는 과정을 예시로 들어보면 아래와 같다.

단계 배열 상태 설명
초기 [64, 12, 33, 72, 32] 정렬되지 않은 배열
Cycle 1 [12, 64, 33, 72, 32] 64와 12 교환
Cycle 1 [12, 33, 64, 72, 32] 64와 33 교환
Cycle 1 [12, 33, 64, 72, 32] 64와 72 비교 (교환 없음)
Cycle 1 [12, 33, 64, 32, 72] 72와 32 교환
Cycle 1 종료 Cycle 1 종료 가장 큰 값 72가 맨 뒤로 이동
Cycle 2 [12, 33, 64, 32, 72] 12와 33 비교 (교환 없음)
Cycle 2 [12, 33, 64, 32, 72] 33와 64 비교 (교환 없음)
Cycle 2 [12, 33, 32, 64, 72] 64와 32 교환
Cycle 2 종료 Cycle 2 종료 64가 뒤에서 두 번째로 이동
Cycle 3 [12, 33, 32, 64, 72] 12와 33 비교 (교환 없음)
Cycle 3 [12, 32, 33, 64, 72] 33와 32 교환
Cycle 3 종료 Cycle 3 종료 33이 정렬된 위치로 이동
Cycle 4 [12, 32, 33, 64, 72] 12와 32 비교 (교환 없음)
Cycle 4 종료 Cycle 4 종료 이미 정렬된 상태로 전환됨

사이클 과정을 보면 알다시피, n개의 원소를 가진 배열의 순회(사이클)은 총 (n-1)번 반복된다. 이유는, 각 사이클마다 가장 큰 원소가 뒤로 이동하는데 (n-1)번까지 진행했을 때 가장 앞에 있는 원소가 가장 작은 원소가 되기 때문이다.

구현 예시

Python 구현

def bubble_sort(arr):
  n = len(arr)
    for i in range(n):
      for j in range(n - i - 1):
        if arr[j] > arr[j + 1]:
          arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    
  return arr
            
array = [64, 34, 25, 12, 22, 11, 90]
print('정렬 전:', array)
print('정렬 후:', bubble_sort(array.copy()))

구현 자체는 어렵지가 않다. 사이클마다 처음부터 마지막 원소까지 순회하면서, 원하는 정렬 기준에 맞지 않으면 교환하면 되기 때문이다. 위의 예시는 오름차순으로 정렬하는 예시이다. 출력은 아래와 같다.

출력 결과
정렬 전: [64, 34, 25, 12, 22, 11, 90] 정렬 후: [11, 12, 22, 25, 34, 64, 90]

시간복잡도 분석

시간복잡도를 분석해보자.

  1. 원소가 n개일 때, (n-1)번의 사이클을 진행한다.
  2. 각 사이클에서, 처음부터 마지막까지 (n - i - 1)번 비교를 진행한다.
  3. 따라서 총 비교 횟수는 (n-1) + (n-2) + ... + 1 = n(n-1)/2 번이 된다.
  4. 원소끼리의 교환을 해야하는 경우는 최대 각 사이클마다 (n-1)번이다.

1, 2, 3, 4번에 의해 시간복잡도는 O(n²)이 된다.

위 방법으로 진행된 버블 정렬 알고리즘은 최선의 경우에도 O(n²)의 시간복잡도를 가진다.

알고리즘을 더 최적화시킬 방법은 없을까? 아래 최적화 기법을 살펴보자.

최적화 기법

1. Early Termination

한 번의 순회에서 교환이 일어나지 않았다면 이미 정렬된 상태라는 의미이다. 이를 활용하여, 불필요한 반복을 줄일 수 있다.

def bubble_sort(arr):
  n = len(arr)
    for i in range(n):
      swapped = False
      for j in range(n - i - 1):
        if arr[j] > arr[j + 1]:
          arr[j], arr[j + 1] = arr[j + 1], arr[j]
          swapped = True
      if not swapped:
        break
    return arr
        
array = [64, 34, 25, 12, 22, 11, 90]
print('정렬 전:', array)
print('정렬 후:', bubble_sort(array.copy()))

이전 코드와 비교했을 때, boolean값인 swapped를 추가했다. 하나의 사이클동안 교환이 일어나지 않으면 그 즉시 break를 통해 종료된다.

시간복잡도 분석 - 최적화 기법 적용

케이스 시간 복잡도 설명
최선의 경우 O(n) 이미 정렬된 배열 (Early termination)
평균의 경우 O(n²) 일반적인 경우
최악의 경우 O(n²) 역순으로 정렬된 배열

특징

정렬 순서를 보장하는 Stable Sort이다.

정렬 시 추가적인 메모리 공간이 거의 필요 없는 In-place Sort이다.

Stable Sort와 In-place Sort에 대해서는 아래 글 참고

장단점

장점

단점

버블 정렬은 교육 목적으로는 훌륭하지만, 실제 JAVA를 활용하는 프로젝트에서는 Array.sort(), Collections.sort() 등의 최적화된 정렬 함수를 사용하는 것이 좋습니다.

버블 정렬은 알고리즘을 이해하는데 매우 중요하다. 복잡한 알고리즘을 배우기 전에 이 버블 정렬부터 구현해보자!

관련 글