버블 정렬(Bubble Sort)

버블 정렬(Bubble sort)

• 단순 정렬(Simple sort) 중 하나로, 속도는 느린 편(평균적으로 O(n^2), quadratic time)이지만 간단하게 구현할 수 있는 장점이 있다. 마치 버블이 이동하듯이 가장 큰 수가 왼쪽에서 오른쪽(배열의 앞에서 뒷쪽)으로 이동한다고 해서 버블 정렬이다.

가정

• 버블소트는 배열(Array) 정렬을 가정한다.
• 정렬되지 않은 배열을 오름차순으로 정렬한다.
• 배열의 길이는 n이다.

순서

• 배열의 가장 처음부터(index 0부터) 원소 2개씩 비교 한다.

• 즉 arr[0], arr[1]을 비교해서 arr[0] > arr[1] 이면 순서를 바꾼다. 아니면 그냥 Pass한다.

• arr[1]과 arr[2]에도 똑같이 한다.

• arr[n-2]과 arr[n-1]까지 똑같이 한다. 즉 총 n-1번, 바로 뒤의 원소와 대소비교를 해서 교환을 하거나 하지 않는다.

• 배열의 앞에서부터 끝까지 이렇게 한 번 훑으며 교환을 하는 과정을 패스스루(pass through) 라고 한다.

• 패스스루 과정에서 교환이 1번이라도 일어났다면, 다시 index 0부터 패스스루를 진행한다.

• 패스스루 중 단 한번도 교환이 일어나지 않는다는 것은 모든 원소가 정렬되어 있다는 의미이므로, 이 때 loop를 종료한다.

• 또는 패스스루가 일어날 수 있는 최대 횟수인 n-1번이 되면 loop를 종료한다.

버블정렬의 시간복잡도 계산하기

• 패스스루의 목적은 정렬되지 않은 값 중 가장 큰 값(버블)을 맨 뒤로 위치시키는 것이다.

• 패스스루는 최악의 경우 n-1번 반복된다. 원소가 단 2개라고 했을 때 한 번의 패스스루로 더 큰 값을 뒤에 위치시키면 정렬이 완료되는 것을 생각해보면 쉽다. 원소가 총 n개 일 때, n-1번의 패스스루를 하면 큰 원소부터 뒤에 위치하게 되고, 마지막 남은 하나는 당연히 제일 작은 값이므로 신경쓸 필요 없이 정렬이 완료된다.

• 패스스루를 진행할 때마다 직전 패스스루의 버블은 제외하고 진행한다. 예를 들어 정렬되지 않은 상태에서 첫 번째 패스스루는 가장 큰 값을 맨 뒤에 위치시키는 것을 보장하므로, 이 다음 패스스루에서는 총 원소에서 2번째로 큰 값(정렬되지 않은 원소들 중에서는 제일 큰 값)을 바로 그 앞에 위치시키는 것만 신경쓰면 된다.

• 첫 번째 패스스루에서는 n-1번의 비교가 일어난다. 두 번째 패스스루에서는 직전 버블을 제외하고 진행하므로 n-2번의 비교가 일어난다. 그리고 패스스루는 최대 n-1번 일어나므로, 총 비교 횟수는 (1 + 2 + 3 .... + n - 2 + n - 1) = n(n-1) / 2 이다. (1부터 n까지의 합은 n(n+1)/2 이므로)

  • 1번째 패스스루 비교 횟수: n-1
  • 2번째 패스스루 비교 횟수: n-2
  • 3번째 패스스루 비교 횟수: n-3
  • ...
  • n-1번째 패스스루 비교 횟수: 1
  • 총 비교 횟수 합계: n(n-1)/2

• 그리고 최악의 경우에는 비교할 때마다 교환이 일어나므로, 최대 교환 횟수 역시 n(n-1)/2 이다.

• 그러므로 비교와 교환을 합하면 총 n(n-1)의 연산이 필요하고, 시간복잡도는 상수를 무시하므로 O(n^2)로 정리할 수 있다.

구현 - 파이썬

def bubble_sort(list):
  # 패스스루할 구간을 정해주는 변수(decrement할 변수)
  unsorted_until_index = len(list)-1
  # 정렬 여부를 표시. 패스스루할 동안 교환이 일어났으면 False, 일어나지 않았으면 정렬된 것이므로 True
  sorted = False 

  # 탈출조건
  # 패스스루할 동안 교환이 한 번도 일어나지 않는 경우
  # 또는 총 len(list)-1 번의 패스스루가 진행된 경우
  while not sorted:
    sorted = True 
    # 패스스루 시작
    for i in range(unsorted_until_index):
      # 대소비교 후 교환
      if list[i] > list[i+1]:
        # 교환이 일어났기 때문에 아직 loop 종료하면 안 됨 
        sorted = False 
        list[i], list[i+1] = list[i+1], list[i]
        unsorted_until_index -= 1 

  return list

주의점

버블소트는 셀렉션 소트(선택정렬)랑 평균적으로는 빅오표기법에 의한 속도가 같지만, 실제로 어떤 정렬이 더 좋을지는 세부적인 전제들을 따져봐야 한다.

예를 들어 버블소트와 선택정렬에는 기본적으로 원소 간 비교와 교환이 포함되는데, 이 중 교환에 시간이 오래 걸린다면 어떤 정렬 알고리즘이 더 효율적일 가능성이 높을까? 이런 경우에는 선택정렬을 택하는 것이 더 안전할 것이다.

왜냐하면 선택정렬은 길이가 n인 배열 정렬에서 n-1번을 탐색하고, 최대 n-1번의 교환을 한다. 즉 배열을 전체 탐색(패스 스루)할 때마다 최대 1번의 교환이 일어나므로 총 n-1번의 교환을 넘지 않는다.

반면 버블소트는 길이가 n인 배열에서 최대 n(n-1)/2 만큼의 교환이 일어날 수 있다. 매번 패스스루할 때마다, 비교하는 모든 원소 간 교환이 일어난다는 최악의 경우(내림차순으로 정렬된 경우)를 가정할 때 그렇다.