파이썬 코딩테스트 강좌, 버블 소트 프로그램 1

본 강좌는 파이썬을 이용한 기본적인 알고리즘 문제 풀이 과정에 대해 설명합니다.
이번 시간에는 가장 기초적인 정렬 알고리즘 중 하나인 버블 소트(Bubble Sort)에 대해 자세히 보겠습니다.
버블 소트는 단순하지만 이해하기 쉬운 정렬 알고리즘으로, 알고리즘의 기초를 이해하는 데 많은 도움이 됩니다.

1. 버블 소트란?

버블 소트는 인접한 두 원소를 비교하여 정렬하는 방식으로 동작하는 알고리즘입니다.
순차적으로 리스트의 모든 요소를 반복하면서, 두 개의 인접한 원소가 잘못된 순서에 있는 경우 이들을 교환합니다.
이 과정을 반복하면서 가장 큰 요소가 리스트의 끝으로 “버블”처럼 올라온다는 특징 때문에 이 이름이 붙었습니다.

1.1. 버블 소트의 동작 과정

버블 소트의 기본적인 동작 과정은 다음과 같습니다:

리스트의 첫 번째 요소부터 시작하여 두 개의 인접한 요소를 비교합니다.
첫 번째 요소가 두 번째 요소보다 큰 경우, 두 요소의 위치를 교환합니다.
리스트의 끝까지 반복하여 가장 큰 요소를 맨 끝으로 보냅니다.
리스트의 끝 요소를 제외하고, 다시 1단계로 돌아가 나머지 부분에 대해 반복합니다.
리스트의 모든 요소가 정렬될 때까지 이 과정을 반복합니다.

2. 버블 소트 알고리즘 구현하기

이제 버블 소트를 파이썬 코드로 구현해 보겠습니다. 다음은 버블 소트 알고리즘의 기본적인 코드입니다.

def bubble_sort(arr):
    n = len(arr)
    # 리스트 길이만큼 반복
    for i in range(n):
        # 각 패스에서 마지막 i개 요소는 이미 정렬되었으므로, n-i-1까지 반복
        for j in range(0, n-i-1):
            # 인접한 두 요소를 비교하고 교환
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

2.1. 코드 설명

위 코드는 bubble_sort라는 함수를 정의하고, 이 함수는 정렬할 리스트를 인자로 받습니다.

n = len(arr): 주어진 리스트의 길이를 저장합니다.
외부 for 루프는 리스트의 모든 요소에 대한 패스를 반복합니다.
내부 for 루프는 현재 남아있는 정렬되지 않은 부분에서 인접한 요소를 비교하고, 필요한 경우 교환합니다.
모든 패스가 완료된 후 정렬된 리스트를 반환합니다.

3. 예제와 함께하는 버블 소트

실제로 버블 소트를 사용하여 하나의 예제를 통해 살펴보겠습니다.

3.1. 예제 리스트

다음과 같은 리스트를 정렬해 보겠습니다: [64, 34, 25, 12, 22, 11, 90]

3.2. 정렬 과정 단계별 설명

1. 첫 번째 패스:

64과 34 비교 → 교환 → [34, 64, 25, 12, 22, 11, 90]
64과 25 비교 → 교환 → [34, 25, 64, 12, 22, 11, 90]
64과 12 비교 → 교환 → [34, 25, 12, 64, 22, 11, 90]
64과 22 비교 → 교환 → [34, 25, 12, 22, 64, 11, 90]
64과 11 비교 → 교환 → [34, 25, 12, 22, 11, 64, 90]
64과 90 비교 → 교환 없음 → [34, 25, 12, 22, 11, 64, 90]

가장 큰 수인 90은 맨 끝으로 올라갔습니다.

2. 두 번째 패스:

34과 25 비교 → 교환 → [25, 34, 12, 22, 11, 64, 90]
34과 12 비교 → 교환 → [25, 12, 34, 22, 11, 64, 90]
34과 22 비교 → 교환 → [25, 12, 22, 34, 11, 64, 90]
34과 11 비교 → 교환 → [25, 12, 22, 11, 34, 64, 90]
34과 64 비교 → 교환 없음 → [25, 12, 22, 11, 34, 64, 90]

두 번째로 큰 수인 64가 두 번째로 맨 끝으로 올라갔습니다.

이와 같은 과정을 반복하여 최종적으로 정렬된 리스트 [11, 12, 22, 25, 34, 64, 90]를 얻을 수 있습니다.

4. 시간 복잡도

버블 소트의 시간 복잡도는 최악의 경우 O(n²)입니다. 이는 리스트의 길이 \( n \)에 대해 그 제곱에 비례하는 시간이 소요된다는 의미입니다.
하지만 이미 정렬된 리스트를 처리하는 경우 최선의 경우 O(n)으로 줄어들 수 있습니다.
이는 첫 번째 패스에서 어떤 교환도 발생하지 않기 때문입니다.

5. 버블 소트의 개선점

버블 소트는 구현이 간단한 장점이 있지만, 효율성이 떨어지는 단점이 있습니다.
실제 사용에서는 다음과 같은 개선 방법을 사용할 수 있습니다:

교환이 발생하지 않은 경우 즉시 정렬을 종료하여 불필요한 반복을 줄이는 방법을 사용할 수 있습니다.
최대 패스 진행 시 마지막 범위까지 계속 비교하지 않고 이미 정렬된 범위를 줄일 수 있습니다.

6. 결론

이번 시간에는 버블 소트의 기본 개념과 이를 파이썬으로 구현하는 방법에 대해 배웠습니다.
버블 소트는 단순한 알고리즘이지만, 정렬 개념을 이해하는 데 매우 유용합니다.
알고리즘의 기초를 다지고 싶다면 버블 소트를 이해하는 것으로 시작해 보세요!