[알고리즘] 버블 정렬

버블 소트는 인접한 두 원소를 비교해가며 더 큰 값을 한 쪽 끝으로 밀어 올리는 정렬 알고리즘이다. 가장 단순하고 직관적인 알고리즘이라 정렬의 기본 개념을 이해하는 데 매우 유용하다. 마치 큰 거품이 물 위로 차례로 떠오르는 모습과 같다며 해당 이름이 붙었다.

정렬 과정 (오름차순)

1. 한 번 순회할 때 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를 등 계속 마지막 바로 전 원소와 마지막 원소와 비교하여 가장 큰 값을 오른쪽 끝으로 이동한다.
2. 한 번 순회할 때 생긴 오른쪽 끝의 가장 큰 값은 고정되어 다시 비교할 필요가 없다.
3. 정렬이 완료될 때까지 반복한다.

파이썬 코드

def bubble_sort(arr):
    n = len(arr)
    for i in range (n):
        for j in range(1, n-i):
            if(arr[j-1] > arr[j]):
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr

arr = [5, 4, 3, 2 , 1]
print(*bubble_sort(arr))

시간 복잡도

(n-1) + (n-2) + (n-3) + … + 2 + 1 = n(n-1)/2이므로 시간 복잡도는 $O(N^2)$이다. 정렬이 되어있던 안 되어있던 항상 2개의 원소를 비교해야하므로 최선/평균/최악 시간 복잡도가 모두 $O(N^2)$으로 동일히다.

장점

1. 구현이 매우 간단하다.
   • 알고리즘 구조가 직관적이고 코드가 짧아서 정렬 알고리즘 입문에 적합하다.
2. 안정 정렬(Stable Sort)
   • 동일한 값의 상대적 순서를 유지한다. 즉, (이름, 점수)에서 점수를 기준으로 정렬할 때 이름 순서가 유지된다.
3. 메모리 측면에서 효율적이다.
   • 교환이 배열 안에서 직접 발생하므로 추가 메모리 공간이 필요하지 않다.

단점

1. 시간 복잡도가 비효율적이다.
   • 시간 복잡도가 $O(N^2)$이므로 데이터 크기가 커질수록 비효율적이다.
2. 교환 횟수가 많다.
   • 인접 원소를 계속 교환하기 때문에 불필요한 swap 연산이 매우 많다.

개선된 버블 정렬

• 배열이 이미 정렬되어 있으면 불필요한 반복을 중단하는 방법이다.
• 한 번의 순환동안 swap이 한 번도 일어나지 않았으면 이미 정렬이 완료되었다는 뜻이므로 반복문을 더 돌릴 필요가 없다.

def bubble_sort(arr):
    n = len(arr)
    for i in range (n-1):
        swapped = False
        for j in range(1, n-i):
            if(arr[j-1] > arr[j]):
                arr[j-1], arr[j] = arr[j], arr[j-1]
                swapped = True
        if not swapped:
            break
    return arr

arr = [5, 4, 3, 2 , 1]
print(*bubble_sort(arr))

• 시간 복잡도
  • 이미 정렬된 경우 → 최선 시간 복잡도 O(n)