[Algorithm] 버블 정렬(Bubble Sort) (with Python)

안녕하세요, 성조입니다.

이번 포스팅은 버블 정렬(Bubble Sort)에 대해서 정리해 봅니다.

 

혹여나 올바르지 못한 지식 전달이 있다면 언제든지 댓글 남겨주시면 감사드리겠습니다.

---

버블 정렬(Bubble Sort)이란?

인접한 두 요소를 비교하고 순서가 잘못되었다면 위치를 교환하여 정렬하는 과정을 반복하는 것을 말한다.

 

 

[구현 코드]

def bubble_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                # 인접한 두 요소의 위치를 교환한다.
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# 정렬할 배열
arr = [60, 40, 50, 10, 20, 30]

print("정렬 전 배열:", arr) # [60, 40, 50, 10, 20, 30]

bubble_sort(arr)

print("정렬 후 배열:", arr) # [10, 20, 30, 40, 50, 60]

위 코드를 기준으로 이어서 동작 방식을 설명한다.

 

 

[동작 방식]

 

위는 오름차순 기준으로 정렬한 것이다.

위와 같이 60이 가장 큰 값이므로 오른쪽으로 가장 오른쪽에 존재한다.

 

1 회차 [첫 번째 가장 큰 요소의 값을 찾음.]

[60, 40, 50, 10, 20, 30] -> [40, 60, 50, 10, 20, 30]

[40, 60, 50, 10, 20, 30] -> [40, 50, 60, 10, 20, 30]

[40, 50, 60, 10, 20, 30] -> [40, 50, 10, 60, 20, 30]

[40, 50, 10, 60, 20, 30] -> [40, 50, 10, 20, 60, 30]

[40, 50, 10, 20, 60, 30] -> [40, 50, 10, 20, 30, 60]

 

2 회차 [두 번째 큰 요소의 값을 찾음.]

[40, 50, 10, 20, 30, 60] -> [40, 50, 10, 20, 30, 60] (변경된 상태의 40과 50을 비교했는데 40이 50보다는 작아서 그대로 둔다.

[40, 50, 10, 20, 30, 60] -> [40, 10, 50, 20, 30, 60]

[40, 10, 50, 20, 30, 60] -> [40, 10, 20, 50, 30, 60]

[40, 10, 20, 50, 30, 60] -> [40, 10, 20, 30, 50, 60] 

 

3 회차 [세 번째 큰 요소의 값을 찾음.]

[40, 10, 20, 30, 50, 60] -> [10, 40, 20, 30, 50, 60]

[10, 40, 20, 30, 50, 60] -> [10, 20, 40, 30, 50, 60]

[10, 20, 40, 30, 50, 60] -> [10, 20, 30, 40, 50, 60] (40은 50보다 작기 때문에 끝.)

 

4 회차 [네 번째 큰 요소의 값을 찾음.]

[10, 20, 30, 40, 50, 60] -> [10, 20, 30, 40, 50, 60] (10은 20보다 작기 때문에 변경되지 않는다.)

[10, 20, 30, 40, 50, 60] -> [10, 20, 30, 40, 50, 60] (20은 30보다 작기 때문에 변경되지 않는다.)

 

5 회차

 [10, 20, 30, 40, 50, 60] -> 30과 40의 두 값을 비교해도 30은 40보다 작기 때문에 변경되지 않는다.

 

 

[시간 복잡도]

O^2의 시간 복잡도를 가지고 있다. 하지만 코드가 단순하여 쉽게 활용할 수 있는 코드이다.

 

---

오타 또는 궁금한 부분이 있다면 언제든지 댓글 달아주시면 최대한 답변드리겠습니다.

 

다음 포스팅 때 뵙겠습니다. 감사합니다.