10. 파이썬 기초 알고리즘: 정렬 & 탐색 구현

Bubble, Selection, Insertion, Merge, Quick 정렬 알고리즘과 선형/이진 탐색 구현을 예제와 시간 복잡도 해설과 함께 정리했습니다.

1. Bubble Sort (버블 정렬)

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]

data = [5,1,4,2,8]
bubble_sort(data)
print(data)  # [1,2,4,5,8]

O(n²) 시간 복잡도지만 개념이 단순해 학습용으로 자주 사용됩니다.

2. Selection Sort (선택 정렬)

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

매 단계에서 최소값을 선택해 O(n²)의 시간 복잡도를 가집니다.

3. Insertion Sort (삽입 정렬)

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

대체로 O(n²)이지만, 이미 정렬된 배열에 대해서는 O(n) 성능을 가집니다.

4. Merge Sort (병합 정렬)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        merged.append(left[i] if left[i] < right[j] else right[j])
        i += left[i] < right[j]
        j += left[i] >= right[j]
    merged += left[i:] + right[j:]
    return merged

O(n log n) 안정 정렬이며 큰 데이터 처리에 유용한 병합 기반 알고리즘입니다.

5. Quick Sort (퀵 정렬)

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)

평균 O(n log n), 최악 O(n²)이며, Python 표준 정렬의 핵심 아이디어입니다.

6. Linear & Binary Search (선형 탐색 및 이진 탐색)

def linear_search(arr, target):
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1

def binary_search(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

선형 탐색은 O(n), 이진 탐색은 정렬된 리스트에서 O(log n)입니다.

요약

• **Bubble / Selection / Insertion Sort**: 이해하기 쉬우나 O(n²) 시간 복잡도
• **Merge / Quick Sort**: 평균 O(n log n) 효율적인 정렬 알고리즘
• **Linear Search**: 순차 탐색 O(n)
• **Binary Search**: 정렬된 배열에서 O(log n) 탐색

2부의 마지막 글로, 이번 편에서는 파이썬에서 가장 많이 사용되는 기초 알고리즘을 정리했습니다. 이번 글을 통해 정렬과 탐색의 원리와 구현 방식을 이해하셨길 바랍니다.