[Algorithm] 버블 정렬(Bubble Sort) 이란?

버블 정렬 (Bubble Sort)

버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다.

 

버블 정렬의 특징은 다음과 같다.

 

• 계속 정렬 여부를 플래그 비트(f)로 결정한다.
• 평균과 최악 모두 수행 시간 복잡도는 O(n^2) 이다.
• 회전을 수행할 때마다 가장 큰 값의 레코드가 맨 뒤로 이동하므로 다음 회전에서는 맨 끝에 있는 레코드는 정렬하지 않는다.
  • 예를 들어 [8, 5, 6, 2, 4] 라는 5의 길이를 가지고 있는 배열이 있다고 가정해보면
  • 1회전이 끝나면 8이라는 값은 맨 뒤로 정렬된다.
  • 따라서 2회전 때에는 길이 5를 n 이라고 했을 때 n-1 번째 까지만 정렬 알고리즘을 수행하면 된다.
• i 번째와 i+1 번째를 비교했을 때 i > i+1 이면 자리를 서로 교환한다.

예제를 통해서 버블 정렬을 이해해보자.

버블 정렬 예제

• 초기 상태 : [8, 5, 6, 2, 4]

1 회전

• 첫 번째 레코드(8)와 두 번째 레코드(5)을 비교하여 첫 번째 레코드가 값이 크므로 교환한다.
• 두 번째 레코드(8)와 세 번째 레코드(6)을 비교하여 두 번째 레코드가 값이 크므로 교환한다.
• 세 번째 레코드(8)와 네 번째 레코드(2)을 비교하여 세 번째 레코드가 값이 크므로 교환한다.
• 네 번째 레코드(8)와 다섯 번째 레코드(4)을 비교하여 네 번째 레코드가 값이 크므로 교환한다.
• 1회전 후 정렬 상태 : [5, 6, 2, 4, 8]

2 회전

• 첫 번째 레코드(5)와 두 번째 레코드(6)을 비교하여 첫 번째 레코드가 값이 작으므로 교환하지 않는다.
• 두 번째 레코드(6)와 세 번째 레코드(2)을 비교하여 두 번째 레코드가 값이 크므로 교환한다.
• 세 번째 레코드(6)와 네 번째 레코드(4)을 비교하여 세 번째 레코드가 값이 크므로 교환한다.
• 다섯 번째 레코드는 1회전이 끝났으므로 비교하지 않는다. (n-1 번째 까지 수행)
• 2회전 후 정렬 상태 : [5, 2, 4, 6, 8]

3 회전

• 첫 번째 레코드(5)와 두 번째 레코드(2)을 비교하여 첫 번째 레코드가 값이 크므로 교환한다.
• 두 번째 레코드(5)와 세 번째 레코드(4)을 비교하여 두 번째 레코드가 값이 크므로 교환한다.
• 네 번째 레코드는 2회전이 끝났으므로 비교하지 않는다. (n-2 번째 까지 수행)
• 3회전 후 정렬 상태 : [2, 4, 5, 6, 8]

4 회전

• 첫 번째 레코드(2)와 두 번째 레코드(4)을 비교하여 첫 번째 레코드가 값이 작으므로 교환하지 않는다.
• 세 번째 레코드는 3회전이 끝났으므로 비교하지 않는다. (n-3 번째 까지 수행)
• 4회전 후 정렬 상태 : [2, 4, 5, 6, 8]

버블삽입 정렬 파이썬(Python) 코드

def bubble_sort(A):
    for i in range(len(A)-1, 0, -1): # 회전을 할 때마다 계속 정렬 범위를 줄여나간다.
        for j in range(i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

        print("{} 회전 후 배열 상태 : {}".format(len(A)-i, A))

A = [8, 5, 6, 2, 4]
bubble_sort(A)

코드 수행 결과는 다음과 같다.