검색과 정렬 알고리즘 총정리 (선형·이진 검색 및 5대 정렬 알고리즘)

앞서 파이썬의 고급 자료구조(이터레이터, 제너레이터, 트리, 그래프 등)를 살펴보았습니다. 이번 글에서는 데이터를 효율적으로 찾고 정렬하는 컴퓨터 과학의 핵심인 검색 알고리즘(Search Algorithms)과 정렬 알고리즘(Sorting Algorithms)의 모든 것을 완벽하게 파헤쳐 보겠습니다.

1. 검색 알고리즘 (Search Algorithms)

검색 알고리즘은 데이터 구조 내에서 특정 항목을 찾는 방법을 다룹니다.

A. 선형 검색 (Linear Search)

데이터 집합을 처음부터 끝까지 순차적으로 검사하여 원하는 항목을 찾습니다.

  • 작동 방식: 리스트의 첫 번째 요소부터 마지막 요소까지 하나씩 비교합니다.

  • 시간 복잡도:

    • 최악/평균: $O(n)$ (전체 리스트를 모두 확인해야 할 수 있음)

    • 최선: $O(1)$ (찾는 요소가 첫 번째에 있을 경우)

  • 파이썬 활용: 파이썬의 in 연산자나 .index() 메서드는 내부적으로 선형 검색과 유사한 방식으로 작동합니다.

data = [4, 2, 7, 1, 9]
if 7 in data:
    print("7을 찾았습니다.")

B. 이진 검색 (Binary Search)

데이터 집합이 정렬되어 있을 때만 사용할 수 있는 매우 효율적인 검색 방법입니다.

  • 작동 방식:

    1. 중앙(Mid) 요소를 확인합니다.

    2. 찾는 값이 중앙 값보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 탐색합니다.

    3. 이 과정을 반복하며 탐색 범위를 절반씩 줄입니다.

  • 시간 복잡도: $O(\log n)$ (매우 빠름)

  • 파이썬 활용: 파이썬 표준 라이브러리의 bisect 모듈을 사용하면 정렬된 리스트에서 효율적인 이진 검색 및 삽입을 수행할 수 있습니다.

import bisect
sorted_data = [10, 20, 30, 40, 50]

# 30이 들어갈 위치를 반환 (인덱스 2)
index = bisect.bisect_left(sorted_data, 30) 
print(f"30의 예상 위치: {index}")

2. 정렬 알고리즘 (Sorting Algorithms)

정렬 알고리즘은 데이터를 일정한 순서(오름차순, 내림차순)로 배열하는 방법을 다룹니다.

A. 파이썬 내장 정렬 (Timsort)

파이썬은 list의 .sort() 메서드와 내장 함수 sorted()를 통해 매우 빠르고 안정적인 정렬을 제공합니다. 이들은 Timsort라는 알고리즘을 사용합니다.

  • Timsort: 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)의 장점을 결합한 하이브리드 알고리즘입니다. 실제 데이터에서 매우 효율적입니다.

  • 시간 복잡도: $O(n \log n)$ (매우 빠름)

# 1. 리스트의 내용을 직접 변경 (in-place)
my_list = [5, 2, 8, 1]
my_list.sort()  # my_list는 [1, 2, 5, 8]이 됨
print(my_list)

# 2. 새로운 정렬된 리스트를 반환 (원본 유지)
original_list = [5, 2, 8, 1]
new_list = sorted(original_list) # new_list는 [1, 2, 5, 8], original_list는 그대로 유지
print(original_list)
print(new_list)

B. 주요 구현 정렬 알고리즘 요약

파이썬에서 직접 구현하여 교육용이나 특정 상황에서 사용하는 기본적인 정렬 알고리즘들입니다.

알고리즘 작동 원리 평균 시간 복잡도 비고
선택 정렬 (Selection Sort) 리스트에서 가장 작은(또는 큰) 요소를 찾아 맨 앞으로 교환하며 정렬합니다. $O(n^2)$ 데이터 크기가 작을 때 유용합니다.
삽입 정렬 (Insertion Sort) 각 요소를 이미 정렬된 부분의 올바른 위치에 삽입하며 정렬합니다. $O(n^2)$ 데이터가 거의 정렬되어 있을 때 빠릅니다 ($O(n)$).
버블 정렬 (Bubble Sort) 인접한 두 요소를 비교하여 위치를 바꾸는 과정을 반복하며 가장 큰 요소가 끝으로 이동합니다. $O(n^2)$ 구현이 매우 쉽지만 비효율적입니다.
병합 정렬 (Merge Sort) 리스트를 절반으로 나누고, 재귀적으로 정렬한 뒤, 다시 합치는(병합) 분할 정복 방식입니다. $O(n \log n)$ 안정적이며 최악의 경우에도 성능이 보장됩니다.
퀵 정렬 (Quick Sort) **피벗(Pivot)**을 선택하고, 피벗을 기준으로 데이터를 두 그룹으로 나누어 재귀적으로 정렬합니다. $O(n \log n)$ 일반적으로 가장 빠른 정렬 알고리즘입니다.

1. 선택 정렬 (Selection Sort)

가장 작은(또는 큰) 요소를 찾아 배열의 정렬된 위치로 선택하여 이동시킵니다.

  • 원리: 매 단계마다 남은 배열에서 최소값을 찾아 현재 위치와 교환합니다.

  • 시간 복잡도: $O(n^2)$

수동 실행 예시

  • 1단계: 정렬되지 않은 배열 [7, 12, 9, 11, 3]

  • 2~3단계: 가장 작은 값 3을 찾아 맨 앞으로 이동 [3, 7, 12, 9, 11]

  • 4~8단계: 나머지 요소 중 최소값을 찾아 순차적으로 교환하여 최종 정렬 [3, 7, 9, 11, 12] 완료.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 1. 현재 남은 리스트에서 최소값의 인덱스를 찾음
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                
        # 2. 찾은 최소값과 현재 위치(i)의 요소를 교환
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 예시
data = [64, 25, 12, 22, 11]
print(f"선택 정렬 전: {data}")
selection_sort(data)
print(f"선택 정렬 후: {data}")

2. 삽입 정렬 (Insertion Sort)

데이터를 하나씩 가져와 이미 정렬된 부분의 정확한 위치에 삽입하면서 정렬을 완성합니다.

  • 원리: 카드를 정리하듯, 새 카드를 집어들 때마다 이미 정리된 카드 사이의 올바른 자리에 끼워 넣습니다.

  • 시간 복잡도: $O(n^2)$ (거의 정렬된 데이터의 경우 $O(n)$)

수동 실행 예시

  • 1단계: [7, 12, 9, 11, 3]

  • 2~3단계: 첫 번째 값 7을 정렬된 부분으로 보고 다음 값 12는 그대로 둠 [7, 12, 9, 11, 3]

  • 4~9단계: 9, 11, 3을 차례대로 정렬된 영역 안의 올바른 자리에 삽입하여 최종 정렬 [3, 7, 9, 11, 12] 완성.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i] # 현재 삽입할 요소
        j = i - 1
        
        # 1. key가 정렬된 부분(arr[0..j])의 요소보다 작으면
        # 2. 해당 요소들을 오른쪽으로 한 칸씩 밀어냄
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        
        # 3. key를 올바른 위치에 삽입
        arr[j + 1] = key
    return arr

# 예시
data = [12, 11, 13, 5, 6]
print(f"삽입 정렬 전: {data}")
insertion_sort(data)
print(f"삽입 정렬 후: {data}")

3. 버블 정렬 (Bubble Sort)

인접한 두 요소를 비교하며 위치를 교환하여 가장 큰(또는 작은) 요소가 맨 끝으로 마치 거품처럼 올라오도록 정렬합니다.

  • 원리: 매 단계마다 리스트를 순회하며 인접한 두 요소를 비교하고 순서가 맞지 않으면 교환합니다.

  • 시간 복잡도: $O(n^2)$

수동 실행 예시

  • 1~8단계: [7, 12, 9, 11, 3]에서 인접한 두 값을 비교해 큰 값을 뒤로 보내는 과정을 반복하여 가장 큰 값이 맨 뒤로 이동하도록 스왑 수행.

def bubble_sort(arr):
    n = len(arr)
    # n-1번의 순회를 통해 정렬
    for i in range(n - 1):
        # 마지막 i개 요소는 이미 정렬되었으므로 제외
        for j in range(n - 1 - i):
            # 인접한 요소 비교 후, 앞 요소가 크면 교환
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 예시
data = [5, 1, 4, 2, 8]
print(f"버블 정렬 전: {data}")
bubble_sort(data)
print(f"버블 정렬 후: {data}")

4. 병합 정렬 (Merge Sort)

분할 정복(Divide and Conquer) 방식을 사용하여 리스트를 나누고 정렬한 뒤 합칩니다.

  • 원리: 리스트를 더 이상 나눌 수 없을 때까지 절반씩 나누고, 다시 합치는 과정(Merge)에서 정렬을 수행합니다.

  • 시간 복잡도: $O(n \log n)$ (안정적이며 최악의 경우에도 동일)

수동 실행 예시

  • 1단계: 요소가 하나씩 남을 때까지 절반으로 분할 ([12, 8, 9, 3, 11, 5, 4] $\rightarrow$ [12], [8], [9] 등)

  • 2~12단계: 작은 조각들을 정렬하면서 다시 하나의 배열로 병합(Merge)을 반복하여 최종 정렬 완료.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]  # 왼쪽 절반
        R = arr[mid:]  # 오른쪽 절반
        
        merge_sort(L)  # 왼쪽 재귀 정렬
        merge_sort(R)  # 오른쪽 재귀 정렬

        i = j = k = 0
        # L과 R을 병합하며 정렬
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 남은 요소들을 복사
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
            
    return arr

# 예시
data = [38, 27, 43, 3, 9, 82, 10]
print(f"병합 정렬 전: {data}")
merge_sort(data)
print(f"병합 정렬 후: {data}")

5. 퀵 정렬 (Quick Sort)

역시 분할 정복 방식을 사용하며, 피벗(Pivot)을 기준으로 리스트를 나누어 정렬합니다.

  • 원리: 리스트에서 피벗을 선택하고, 피벗보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 재배치(Partition)한 뒤, 분할된 서브리스트를 재귀적으로 정렬합니다.

  • 시간 복잡도: $O(n \log n)$ (평균), $O(n^2)$ (최악, 피벗 선택이 잘못될 경우)

수동 실행 예시

  • 1~8단계: 배열 [11, 9, 12, 7, 3]에서 마지막 값 3을 피벗으로 지정하고 작고 큰 요소들을 분할·재귀 정렬 수행.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 피벗 선택 (여기서는 간단하게 리스트의 첫 번째 요소를 피벗으로 사용)
    pivot = arr[0]
    tail = arr[1:]
    
    # 피벗을 기준으로 분할
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    
    # 분할된 서브리스트를 재귀적으로 정렬하고 병합
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

# 예시
data = [10, 7, 8, 9, 1, 5]
print(f"퀵 정렬 전: {data}")
sorted_data = quick_sort(data)
print(f"퀵 정렬 후: {sorted_data}")