[파이썬으로 배우는 알고리즘] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)이란?

서로 인접한 두 원소를 비교하고, 순서가 맞지 않으면 교체하는 방식으로 정렬하는 정렬 알고리즘입니다. 원소가 마치 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다고 합니다.

 

---

버블 정렬 과정

위와 같이 정렬되어 있지 않은 배열을 버블 정렬 알고리즘을 사용하여 정렬해보겠습니다.

 

먼저 배열의 맨 앞부터 인접한 원소를 비교합니다. 11은 10보다 크므로 대소 관계를 만족합니다. 따라서 교체하지 않습니다.

 

그다음으로 인접한 11과 2를 비교합니다. 2는 11보다 작으므로 대소 관계를 만족하지 않습니다.

 

따라서 위와 같이 두 원소의 자리를 교체합니다.

 

그다음으로 인접한 11과 4를 비교합니다. 4는 11보다 작으므로 대소 관계를 만족하지 않습니다.

 

따라서 위와 같이 두 원소의 자리를 교체합니다.

 

그다음으로 인접한 11과 4를 비교합니다. 4는 11보다 작으므로 대소 관계를 만족하지 않습니다.

 

따라서 위와 같이 두 원소의 자리를 교체합니다.

 

이 과정으로 배열에서 가장 큰 원소를 맨 뒤로 보냈습니다. 이를 1회전으로 하여 다음 회전부터는 이전 회전에서의 마지막 원소는 제외하고 똑같이 정렬을 진행합니다.

 

2회전입니다. 다음으로 큰 원소인 10이 버블 정렬을 통해 맨 뒤로 이동합니다.

 

3회전입니다. 다음으로 큰 원소인 4가 버블 정렬을 통해 맨 뒤로 이동합니다.

 

4회전입니다. 다음으로 큰 원소인 3이 버블 정렬을 통해 맨 뒤로 이동합니다.

 

이렇게 배열의 모든 원소가 버블 정렬을 통해 정렬이 됩니다.

 

---

버블 정렬 특징

• 간단한 구현
• 최선이든 최악이든 시간 복잡도는 O(N^2)
• 정렬 과정에서 배열에서 값을 바꾸는 식으로 동작하여 공간 복잡도는 O(N). 값을 바꿀 때 임시 공간만 필요하기 때문에 in-place 정렬

---

버블 정렬 구현

코드

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


a = [10, 11, 2, 4, 3]
print('###정렬전###')
print(a)
bubble_sort(a)
print('###정렬후###')
print(a)

결과