버블 정렬 알고리즘 (Bubble Sort)

이번 포스팅에서 다룰 버블 정렬(Bubble Sort)은 거품 정렬이라고도 하는데 속도는 조금 느리지만, 정렬 알고리즘 중에 알고리즘이 단순하고 코드 구현이 쉽기 때문에 자주 사용됩니다. 버블 정렬 과정, 시간 복잡도, 장단점, 버블 정렬 알고리즘 파이썬 구현에 대해 알아보겠습니다.

 

버블 정렬이란? (Bubble Sort)

인접한 두 개의 원소를 비교하며 자리를 교환하여 정렬하는 방법입니다.

교환하는 원소의 이동 모습이 마치 수면 위로 올라오는 거품 같아서 지어진 이름입니다.

 

오름차순 버블 정렬 과정

첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 원소까지 교환합니다.

한 단계가 끝나면 오름차순일 경우는 가장 큰 원소가, 내림차순일 경우 가장 작은 원소가 마지막 자리로 정렬됩니다.

위치 변경 원소, 정렬 대상 원소, 정렬된 원소

 

1회 차 | [25,11,36,7] -> [11,25,36,7] -> [11,25,36,7] -> [11,25,7,36]

2회 차 | [11,25,7,36] -> [11,25,7,36] -> [11,7,25,36]

3회 차 | [11,7,25,36] -> [7,11,25,36]

   끝   | [7,11,25,36]

 

시간 복잡도와 장단점

• 평균 수행 시간: O(n²)
• 최악 수행 시간: O(n²)
• 알고리즘 기법: 비교와 교환
• 장점: 코드 구현이 단순하고 쉽다
• 단점: 속도가 상당히 느리다

버블 정렬 알고리즘 코드

• 두 인접한 원소를 비교하여 앞의 원소가 더 크면 두 원소의 자리를 바꾸어 정렬합니다.
• 아래 코드는 오름차순 정렬 알고리즘입니다.
• 버블 정렬 내림차순은 4번 줄 코드 if list [j] < list [j+1]의 부등호만 바꾸면 됩니다.

def bubble_sort(list):
    for i in range(len(list) - 1, 0, -1):
        for j in range(0, i):
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
        print("{} 회차: {}".format(len(list) - i, list))

a = [25, 11, 36, 7]
bubble_sort(a)

---

버블 정렬 파이썬으로 구현해보고, 거품 정렬의 장단점, 개념, 과정, 시간 복잡도, 알고리즘까지 알아보았습니다.