anonymous.rs

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

5 min read

버블 정렬 (Bubble Sort) 완벽 가이드

소프트웨어 엔지니어링 인터뷰에서 가장 기초적으로 다루는 정렬 알고리즘 중 하나인 **버블 정렬(Bubble Sort)**에 대해 알아보겠습니다. 이름처럼 거품이 수면 위로 올라오는 듯한 모습에서 유래되었습니다.

1. 버블 정렬이란?

버블 정렬은 서로 인접한 두 원소를 비교하여, 크기가 순서대로 되어 있지 않으면 서로 교환(Swap)하는 방식으로 정렬하는 알고리즘입니다.

매 회전(Pass)마다 가장 큰 값이 맨 뒤로 밀려나는 것이 특징입니다.

2. 동작 과정 (오름차순 기준)

  1. 배열의 첫 번째 원소부터 인접한 두 원소(arr[i]와 arr[i+1])를 비교합니다.
  2. 앞의 원소가 뒤의 원소보다 크면 서로 자리를 바꿉니다 (Swap).
  3. 이 과정을 배열의 끝까지 반복하면, 가장 큰 원소가 배열의 맨 끝에 위치하게 됩니다. (1회전 완료)
  4. 마지막 원소(이미 정렬된 원소)를 제외하고 다시 처음부터 같은 과정을 반복합니다.
  5. 더 이상 교환이 일어나지 않을 때까지 반복합니다.

3. 파이썬(Python) 구현 예시

def bubble_sort(arr):
    n = len(arr)
    # 배열의 크기만큼 회전
    for i in range(n):
        # 교환이 일어났는지 확인하는 플래그 (최적화)
        swapped = False
        
        # 매 회전마다 맨 뒤에 정렬된 원소는 제외하고 비교
        for j in range(0, n - i - 1):
            # 인접한 두 원소 비교
            if arr[j] > arr[j + 1]:
                # 자리 교환 (Swap)
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                
        # 한 회전 동안 교환이 한 번도 일어나지 않았다면 이미 정렬 완료
        if not swapped:
            break
            
    return arr
 
# 사용 예시
data = [64, 34, 25, 12, 22, 11, 90]
print("정렬 전:", data)
print("정렬 후:", bubble_sort(data))

4. 시간 복잡도 및 공간 복잡도

  • 시간 복잡도:
    • 최악의 경우 (역순 정렬): (모든 원소를 비교하고 교환해야 함)
    • 최선의 경우 (이미 정렬됨): (위 코드처럼 swapped 플래그로 최적화한 경우, 한 번만 순회하고 종료)
    • 평균의 경우:
  • 공간 복잡도: (주어진 배열 안에서 교환만 이루어지므로 추가 공간이 필요 없음. 제자리 정렬(In-place Sort))

5. 특징

  • 장점: 구현이 매우 간단하고 코드가 직관적입니다. 제자리 정렬이며, 안정 정렬(Stable Sort, 값이 같은 원소의 상대적 순서가 유지됨)입니다.
  • 단점: 시간 복잡도가 이므로 데이터의 개수가 많아질수록 성능이 기하급수적으로 떨어집니다. 실무에서는 거의 사용되지 않습니다.

요약

버블 정렬은 인접한 데이터를 교환하며 정렬하는 가장 단순한 알고리즘입니다. 실무 효율성은 떨어지지만, 정렬 알고리즘의 기초를 이해하고 코드로 구현하는 능력을 평가하기 위해 인터뷰에서 종종 등장하므로 정확한 동작 원리와 최적화 방법(swapped 플래그)을 기억해 두는 것이 좋습니다.

Graph View