[정렬 알고리즘 비교] 버블, 삽입, 퀵, 병합 정렬

정렬은 데이터를 정해진 순서에 맞게 배열하는 과정으로, 많은 알고리즘이 존재합니다. 그중에서 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬은 기본부터 고급까지 다양한 문제에서 사용됩니다. 이번 포스트에서는 이 네 가지 정렬 알고리즘의 작동 원리와 차이점을 비교해보겠습니다.

---

1. 버블 정렬 (Bubble Sort)

1) 알고리즘 설명

• 인접한 두 요소를 비교하여, 순서가 잘못된 경우 서로 교환합니다.

• 가장 큰 값이 매번 오른쪽 끝으로 “거품처럼 올라가는” 방식입니다.

2) 특징

• 시간 복잡도:
• 최선: O(n) (이미 정렬된 경우).
• 평균 및 최악: O(n²).

• 공간 복잡도: O(1) (제자리 정렬, 추가 메모리 필요 없음).

• 장점: 구현이 간단함.

• 단점: 데이터 크기가 클 경우 비효율적.

3) Python 코드

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        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

# 실행 예시
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

2. 삽입 정렬 (Insertion Sort)

1) 알고리즘 설명

• 배열의 각 요소를 정렬된 부분 배열에 삽입하여 정렬을 확장합니다.

• 카드를 한 장씩 정렬하는 방식과 유사합니다.

2) 특징

• 시간 복잡도:
• 최선: O(n) (이미 정렬된 경우).
• 평균 및 최악: O(n²).

• 공간 복잡도: O(1) (제자리 정렬).

• 장점: 작은 배열이나 거의 정렬된 데이터에서 효율적.

• 단점: 데이터 크기가 클 경우 비효율적.

3) Python 코드

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 실행 예시
print(insertion_sort([64, 34, 25, 12, 22, 11, 90]))

3. 퀵 정렬 (Quick Sort)

1) 알고리즘 설명

• 분할 정복 알고리즘의 일종으로, 배열을 피벗(pivot)을 기준으로 나누고, 각 부분 배열을 재귀적으로 정렬합니다.

2) 특징

• 시간 복잡도:
• 최선 및 평균: O(n log n).
• 최악: O(n²) (이미 정렬된 경우 등).

• 공간 복잡도: O(log n) (재귀 호출 스택).

• 장점: 평균적으로 매우 빠르며, 대부분의 경우 적합.

• 단점: 최악의 경우 성능 저하.

3) Python 코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 실행 예시
print(quick_sort([64, 34, 25, 12, 22, 11, 90]))

4. 병합 정렬 (Merge Sort)

1) 알고리즘 설명

• 분할 정복 알고리즘의 일종으로, 배열을 반으로 나누어 각각 정렬한 후 병합합니다.

2) 특징

• 시간 복잡도:
• 최선, 평균, 최악: O(n log n).

• 공간 복잡도: O(n) (추가 메모리 필요).

• 장점: 안정적이며, 큰 데이터나 외부 정렬에 적합.

• 단점: 추가 메모리를 사용하므로 메모리 제약이 있는 경우 비효율적.

3) Python 코드

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 실행 예시
print(merge_sort([64, 34, 25, 12, 22, 11, 90]))