[CS 기초 #12] 정렬 알고리즘: 버블 정렬부터 퀵 정렬까지 완벽 마스터

정렬의 모든 것! 버블 정렬부터 퀵 정렬까지, 데이터를 빠르게 정렬하는 방법을 배웁니다.

🎯 이 글을 읽고 나면

• 버블, 선택, 삽입 정렬의 원리를 이해합니다
• 병합 정렬과 퀵 정렬을 구현할 수 있습니다
• 각 정렬 알고리즘의 시간 복잡도를 비교할 수 있습니다
• 안정 정렬과 불안정 정렬의 차이를 알게 됩니다
• 상황에 맞는 정렬 알고리즘을 선택할 수 있습니다

📚 사전 지식

• 시간 복잡도: 복잡도 분석 필수
• 재귀 함수: 병합/퀵 정렬에 사용
• 배열 기초: 인덱스, 교환 연산 이해

💡 핵심 개념 미리보기

정렬은 데이터를 순서대로 나열하는 것으로, 검색과 분석의 기초입니다. O(n²)의 단순 정렬(버블/선택/삽입)부터 O(n log n)의 고급 정렬(병합/퀵/힙)까지 다양합니다. Python의 sort()는 Timsort(병합+삽입)를 사용하며, 실무에서는 대부분 O(n log n) 정렬을 씁니다!

---

🎯 들어가며: 정렬이 왜 중요한가?

데이터베이스 인덱싱, 검색 엔진, 추천 시스템, 데이터 분석… 모든 곳에서 정렬이 필요합니다! 구글은 어떻게 수십억 개의 웹페이지를 순식간에 정렬할까요?

오늘은 정렬 알고리즘의 모든 것을 다룹니다. 단순한 버블 정렬부터 효율적인 퀵 정렬, 그리고 특수한 기수 정렬까지 완벽하게 마스터해보겠습니다!

📊 정렬 알고리즘 개요

정렬 알고리즘은 데이터를 특정 순서대로 재배열하는 알고리즘입니다.

graph TB
    subgraph "정렬 알고리즘 분류"
        Simple[단순 정렬<br/>O(n²)]
        Efficient[효율적 정렬<br/>O(n log n)]
        Linear[선형 정렬<br/>O(n)]
    end
    
    Simple --> Bubble[버블 정렬]
    Simple --> Selection[선택 정렬]
    Simple --> Insertion[삽입 정렬]
    
    Efficient --> Quick[퀵 정렬]
    Efficient --> Merge[병합 정렬]
    Efficient --> Heap[힙 정렬]
    
    Linear --> Counting[계수 정렬]
    Linear --> Radix[기수 정렬]
    Linear --> Bucket[버킷 정렬]

정렬 알고리즘 비교표

def sorting_comparison():
    """정렬 알고리즘 비교"""
    
    algorithms = {
        "버블 정렬": {
            "최선": "O(n)",
            "평균": "O(n²)",
            "최악": "O(n²)",
            "공간": "O(1)",
            "안정성": "안정",
            "제자리": "Yes"
        },
        "선택 정렬": {
            "최선": "O(n²)",
            "평균": "O(n²)", 
            "최악": "O(n²)",
            "공간": "O(1)",
            "안정성": "불안정",
            "제자리": "Yes"
        },
        "삽입 정렬": {
            "최선": "O(n)",
            "평균": "O(n²)",
            "최악": "O(n²)",
            "공간": "O(1)",
            "안정성": "안정",
            "제자리": "Yes"
        },
        "퀵 정렬": {
            "최선": "O(n log n)",
            "평균": "O(n log n)",
            "최악": "O(n²)",
            "공간": "O(log n)",
            "안정성": "불안정",
            "제자리": "Yes"
        },
        "병합 정렬": {
            "최선": "O(n log n)",
            "평균": "O(n log n)",
            "최악": "O(n log n)",
            "공간": "O(n)",
            "안정성": "안정",
            "제자리": "No"
        },
        "힙 정렬": {
            "최선": "O(n log n)",
            "평균": "O(n log n)",
            "최악": "O(n log n)",
            "공간": "O(1)",
            "안정성": "불안정",
            "제자리": "Yes"
        }
    }
    
    print("정렬 알고리즘 성능 비교:")
    print("-" * 80)
    print(f"{'알고리즘':<12} {'최선':<12} {'평균':<12} {'최악':<12} {'공간':<10} {'안정성':<8} {'제자리':<8}")
    print("-" * 80)
    
    for name, perf in algorithms.items():
        print(f"{name:<12} {perf['최선']:<12} {perf['평균']:<12} {perf['최악']:<12} "
              f"{perf['공간']:<10} {perf['안정성']:<8} {perf['제자리']:<8}")

sorting_comparison()

🟢 단순 정렬 알고리즘 (O(n²))

1. 버블 정렬 (Bubble Sort)

인접한 두 원소를 비교하며 정렬하는 가장 단순한 알고리즘입니다.

def bubble_sort(arr):
    """버블 정렬 - O(n²)
    인접한 원소를 비교하여 교환
    """
    n = len(arr)
    
    for i in range(n):
        # 이미 정렬된 경우 조기 종료
        swapped = False
        
        # 매 반복마다 가장 큰 원소가 뒤로 이동
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # 교환이 없으면 정렬 완료
        if not swapped:
            break
    
    return arr

def bubble_sort_visualization():
    """버블 정렬 시각화"""
    arr = [64, 34, 25, 12, 22, 11, 90]
    print(f"초기 배열: {arr}")
    n = len(arr)
    
    for i in range(n):
        print(f"\n패스 {i + 1}:")
        swapped = False
        
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                print(f"  교환: {arr[j]} ↔ {arr[j + 1]}")
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                print(f"  → {arr}")
        
        if not swapped:
            print("  정렬 완료!")
            break
    
    print(f"\n최종 배열: {arr}")

bubble_sort_visualization()

2. 선택 정렬 (Selection Sort)

최솟값을 찾아 맨 앞과 교환하는 방식입니다.

def selection_sort(arr):
    """선택 정렬 - O(n²)
    최솟값을 선택하여 앞으로 이동
    """
    n = len(arr)
    
    for i in range(n):
        # 최솟값 인덱스 찾기
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # 최솟값을 현재 위치와 교환
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

def selection_sort_steps():
    """선택 정렬 단계별 표시"""
    arr = [64, 25, 12, 22, 11]
    print(f"초기 배열: {arr}")
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        print(f"\n{i+1}번째 최솟값 찾기:")
        
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        print(f"  최솟값: {arr[min_idx]} (인덱스 {min_idx})")
        
        if min_idx != i:
            print(f"  교환: {arr[i]} ↔ {arr[min_idx]}")
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
        
        print(f"  현재 배열: {arr}")
        print(f"  정렬된 부분: {arr[:i+1]}")

selection_sort_steps()

3. 삽입 정렬 (Insertion Sort)

정렬된 부분에 새로운 원소를 올바른 위치에 삽입합니다.

def insertion_sort(arr):
    """삽입 정렬 - O(n²)
    정렬된 부분에 삽입
    """
    n = len(arr)
    
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        
        # key보다 큰 원소들을 오른쪽으로 이동
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # key를 올바른 위치에 삽입
        arr[j + 1] = key
    
    return arr

def insertion_sort_with_binary_search(arr):
    """이진 검색을 활용한 삽입 정렬"""
    
    def binary_search(arr, val, start, end):
        """삽입 위치를 이진 검색으로 찾기"""
        if start == end:
            return start if arr[start] > val else start + 1
        
        if start > end:
            return start
        
        mid = (start + end) // 2
        
        if arr[mid] < val:
            return binary_search(arr, val, mid + 1, end)
        elif arr[mid] > val:
            return binary_search(arr, val, start, mid - 1)
        else:
            return mid
    
    for i in range(1, len(arr)):
        key = arr[i]
        left = 0
        right = i
        
        # 삽입 위치 찾기
        pos = binary_search(arr, key, left, right - 1)
        
        # 원소들 이동
        arr[pos + 1:i + 1] = arr[pos:i]
        arr[pos] = key
    
    return arr

# 삽입 정렬 활용: 거의 정렬된 데이터
def insertion_sort_best_case():
    """삽입 정렬이 효율적인 경우"""
    import random
    
    # 거의 정렬된 배열
    arr = list(range(100))
    # 약간의 원소만 섞기
    for _ in range(5):
        i, j = random.randint(0, 99), random.randint(0, 99)
        arr[i], arr[j] = arr[j], arr[i]
    
    print("거의 정렬된 배열에서 삽입 정렬은 O(n)에 가까운 성능")
    insertion_sort(arr.copy())
    
    return arr

🚀 효율적인 정렬 알고리즘 (O(n log n))

4. 퀵 정렬 (Quick Sort)

분할 정복 방식으로 피벗을 기준으로 분할하여 정렬합니다.

def quick_sort(arr, low=0, high=None):
    """퀵 정렬 - 평균 O(n log n), 최악 O(n²)"""
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # 분할
        pivot_index = partition(arr, low, high)
        
        # 재귀적으로 정렬
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)
    
    return arr

def partition(arr, low, high):
    """Lomuto 분할 방식"""
    # 마지막 원소를 피벗으로 선택
    pivot = arr[high]
    
    # 피벗보다 작은 원소들의 인덱스
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # 피벗을 올바른 위치로 이동
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort_optimized(arr):
    """최적화된 퀵 정렬"""
    
    def median_of_three(arr, low, high):
        """3개 중앙값으로 피벗 선택"""
        mid = (low + high) // 2
        
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]
        if arr[mid] > arr[high]:
            arr[mid], arr[high] = arr[high], arr[mid]
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]
        
        return mid
    
    def quick_sort_helper(arr, low, high):
        # 작은 배열은 삽입 정렬 사용
        if high - low < 10:
            for i in range(low + 1, high + 1):
                key = arr[i]
                j = i - 1
                while j >= low and arr[j] > key:
                    arr[j + 1] = arr[j]
                    j -= 1
                arr[j + 1] = key
            return
        
        if low < high:
            # 중앙값 피벗 선택
            pivot_idx = median_of_three(arr, low, high)
            arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
            
            # 분할
            pivot_index = partition(arr, low, high)
            
            # 재귀
            quick_sort_helper(arr, low, pivot_index - 1)
            quick_sort_helper(arr, pivot_index + 1, high)
    
    quick_sort_helper(arr, 0, len(arr) - 1)
    return arr

# 3-way 퀵 정렬 (중복 원소가 많을 때)
def quick_sort_3way(arr, low=0, high=None):
    """3-way 퀵 정렬 - 중복 원소 처리"""
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        lt, gt = partition_3way(arr, low, high)
        quick_sort_3way(arr, low, lt - 1)
        quick_sort_3way(arr, gt + 1, high)
    
    return arr

def partition_3way(arr, low, high):
    """3-way 분할"""
    pivot = arr[low]
    i = low
    lt = low
    gt = high
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    
    return lt, gt

5. 병합 정렬 (Merge Sort)

분할 정복 방식으로 배열을 반으로 나누고 병합하며 정렬합니다.

def merge_sort(arr):
    """병합 정렬 - O(n log n)"""
    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

def merge_sort_iterative(arr):
    """반복적 병합 정렬 (Bottom-up)"""
    n = len(arr)
    
    # 크기를 2배씩 증가
    size = 1
    while size < n:
        # 현재 크기로 병합
        for start in range(0, n, size * 2):
            mid = min(start + size, n)
            end = min(start + size * 2, n)
            
            # 병합할 두 부분 배열
            left = arr[start:mid]
            right = arr[mid:end]
            
            # 병합
            merged = merge(left, right)
            arr[start:end] = merged
        
        size *= 2
    
    return arr

def merge_sort_in_place(arr, left=0, right=None):
    """제자리 병합 정렬"""
    if right is None:
        right = len(arr) - 1
    
    if left < right:
        mid = (left + right) // 2
        
        # 분할
        merge_sort_in_place(arr, left, mid)
        merge_sort_in_place(arr, mid + 1, right)
        
        # 제자리 병합
        merge_in_place(arr, left, mid, right)
    
    return arr

def merge_in_place(arr, left, mid, right):
    """제자리 병합"""
    # 임시 배열 생성
    left_part = arr[left:mid + 1]
    right_part = arr[mid + 1:right + 1]
    
    i = j = 0
    k = left
    
    while i < len(left_part) and j < len(right_part):
        if left_part[i] <= right_part[j]:
            arr[k] = left_part[i]
            i += 1
        else:
            arr[k] = right_part[j]
            j += 1
        k += 1
    
    while i < len(left_part):
        arr[k] = left_part[i]
        i += 1
        k += 1
    
    while j < len(right_part):
        arr[k] = right_part[j]
        j += 1
        k += 1

6. 힙 정렬 (Heap Sort)

최대 힙을 구성하고 루트를 추출하며 정렬합니다.

def heap_sort(arr):
    """힙 정렬 - O(n log n)"""
    n = len(arr)
    
    # 최대 힙 구성 - O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 원소 추출 - O(n log n)
    for i in range(n - 1, 0, -1):
        # 루트(최댓값)를 마지막과 교환
        arr[0], arr[i] = arr[i], arr[0]
        
        # 힙 속성 복구
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    """최대 힙 속성 유지"""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 왼쪽 자식이 더 크면
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 오른쪽 자식이 더 크면
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # 교환이 필요하면
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        
        # 재귀적으로 힙 속성 유지
        heapify(arr, n, largest)

def heap_sort_visualization():
    """힙 정렬 시각화"""
    arr = [12, 11, 13, 5, 6, 7]
    print(f"초기 배열: {arr}")
    n = len(arr)
    
    print("\n=== 최대 힙 구성 ===")
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
        print(f"heapify({i}): {arr}")
    
    print(f"\n최대 힙: {arr}")
    
    print("\n=== 정렬 과정 ===")
    for i in range(n - 1, 0, -1):
        print(f"최댓값 {arr[0]}를 마지막으로 이동")
        arr[0], arr[i] = arr[i], arr[0]
        print(f"교환 후: {arr}")
        
        heapify(arr, i, 0)
        print(f"힙 복구: {arr[:i]} | 정렬됨: {arr[i:]}")
        print()
    
    print(f"최종 결과: {arr}")

heap_sort_visualization()

🎨 특수 정렬 알고리즘 (O(n))

7. 계수 정렬 (Counting Sort)

def counting_sort(arr):
    """계수 정렬 - O(n + k), k는 범위"""
    if not arr:
        return arr
    
    # 최댓값과 최솟값 찾기
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1
    
    # 카운트 배열 생성
    count = [0] * range_val
    output = [0] * len(arr)
    
    # 각 원소의 개수 세기
    for num in arr:
        count[num - min_val] += 1
    
    # 누적 합 계산
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 출력 배열 구성 (안정 정렬을 위해 역순)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1
    
    return output

def counting_sort_for_strings(strings, position):
    """문자열의 특정 위치 문자로 계수 정렬"""
    n = len(strings)
    output = [''] * n
    count = [0] * 256  # ASCII 범위
    
    # 카운트
    for string in strings:
        index = ord(string[position]) if position < len(string) else 0
        count[index] += 1
    
    # 누적 합
    for i in range(1, 256):
        count[i] += count[i - 1]
    
    # 출력 배열 구성
    for i in range(n - 1, -1, -1):
        string = strings[i]
        index = ord(string[position]) if position < len(string) else 0
        output[count[index] - 1] = string
        count[index] -= 1
    
    return output

8. 기수 정렬 (Radix Sort)

def radix_sort(arr):
    """기수 정렬 - O(d * n), d는 자릿수"""
    if not arr:
        return arr
    
    # 최댓값의 자릿수 구하기
    max_num = max(arr)
    exp = 1
    
    while max_num // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr

def counting_sort_by_digit(arr, exp):
    """특정 자릿수로 계수 정렬"""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # 자릿수별 카운트
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    
    # 누적 합
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # 출력 배열 구성
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    # 원본 배열에 복사
    for i in range(n):
        arr[i] = output[i]

def radix_sort_strings(strings):
    """문자열 기수 정렬 (MSD)"""
    if not strings:
        return strings
    
    # 최대 길이 구하기
    max_len = max(len(s) for s in strings)
    
    # 뒤에서부터 정렬 (LSD)
    for pos in range(max_len - 1, -1, -1):
        strings = counting_sort_for_strings(strings, pos)
    
    return strings

9. 버킷 정렬 (Bucket Sort)

def bucket_sort(arr):
    """버킷 정렬 - O(n + k)"""
    if not arr:
        return arr
    
    # 버킷 개수
    num_buckets = len(arr)
    max_val = max(arr)
    min_val = min(arr)
    
    # 버킷 생성
    buckets = [[] for _ in range(num_buckets)]
    
    # 원소를 버킷에 분배
    for num in arr:
        index = int((num - min_val) / (max_val - min_val + 1) * num_buckets)
        if index == num_buckets:
            index -= 1
        buckets[index].append(num)
    
    # 각 버킷 정렬
    for bucket in buckets:
        insertion_sort(bucket)
    
    # 버킷 병합
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

def bucket_sort_floats(arr):
    """0~1 사이 실수 버킷 정렬"""
    n = len(arr)
    buckets = [[] for _ in range(n)]
    
    # 버킷에 분배
    for num in arr:
        index = int(n * num)
        if index == n:
            index = n - 1
        buckets[index].append(num)
    
    # 각 버킷 정렬
    for bucket in buckets:
        bucket.sort()
    
    # 병합
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

🔄 하이브리드 정렬

Tim Sort (Python의 기본 정렬)

def tim_sort(arr):
    """Tim Sort 간단 구현"""
    MIN_MERGE = 32
    
    def insertion_sort_tim(arr, left, right):
        """삽입 정렬 (Tim Sort용)"""
        for i in range(left + 1, right + 1):
            key = arr[i]
            j = i - 1
            while j >= left and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = key
    
    def merge_tim(arr, left, mid, right):
        """병합 (Tim Sort용)"""
        left_part = arr[left:mid + 1]
        right_part = arr[mid + 1:right + 1]
        
        i = j = 0
        k = left
        
        while i < len(left_part) and j < len(right_part):
            if left_part[i] <= right_part[j]:
                arr[k] = left_part[i]
                i += 1
            else:
                arr[k] = right_part[j]
                j += 1
            k += 1
        
        while i < len(left_part):
            arr[k] = left_part[i]
            i += 1
            k += 1
        
        while j < len(right_part):
            arr[k] = right_part[j]
            j += 1
            k += 1
    
    n = len(arr)
    
    # 작은 부분을 삽입 정렬로 정렬
    for start in range(0, n, MIN_MERGE):
        end = min(start + MIN_MERGE - 1, n - 1)
        insertion_sort_tim(arr, start, end)
    
    # 병합 시작
    size = MIN_MERGE
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min(start + size * 2 - 1, n - 1)
            
            if mid < end:
                merge_tim(arr, start, mid, end)
        
        size *= 2
    
    return arr

💡 정렬 알고리즘 선택 가이드

def sorting_algorithm_selector(data_info):
    """상황별 최적 정렬 알고리즘 선택"""
    
    recommendations = {
        "작은 데이터 (n < 50)": {
            "알고리즘": "삽입 정렬",
            "이유": "구현이 간단하고 작은 데이터에서 효율적",
            "복잡도": "O(n²)"
        },
        "거의 정렬된 데이터": {
            "알고리즘": "삽입 정렬 또는 Tim Sort",
            "이유": "거의 정렬된 경우 O(n)에 가까운 성능",
            "복잡도": "O(n) ~ O(n²)"
        },
        "일반적인 경우": {
            "알고리즘": "퀵 정렬 또는 Tim Sort",
            "이유": "평균적으로 가장 빠른 성능",
            "복잡도": "O(n log n)"
        },
        "최악의 경우 보장": {
            "알고리즘": "힙 정렬 또는 병합 정렬",
            "이유": "항상 O(n log n) 보장",
            "복잡도": "O(n log n)"
        },
        "안정 정렬 필요": {
            "알고리즘": "병합 정렬 또는 Tim Sort",
            "이유": "동일한 값의 순서 유지",
            "복잡도": "O(n log n)"
        },
        "메모리 제한": {
            "알고리즘": "힙 정렬 또는 퀵 정렬",
            "이유": "제자리 정렬로 추가 메모리 최소화",
            "복잡도": "O(n log n), 공간 O(1)"
        },
        "정수 범위 제한": {
            "알고리즘": "계수 정렬 또는 기수 정렬",
            "이유": "O(n) 시간 복잡도 가능",
            "복잡도": "O(n + k) 또는 O(d * n)"
        },
        "부분 정렬": {
            "알고리즘": "힙 정렬 (상위 K개)",
            "이유": "전체 정렬 없이 상위 원소만 추출",
            "복잡도": "O(n + k log n)"
        }
    }
    
    print("정렬 알고리즘 선택 가이드:")
    print("=" * 60)
    for situation, info in recommendations.items():
        print(f"\n{situation}:")
        for key, value in info.items():
            print(f"  {key}: {value}")
    
    return recommendations

sorting_algorithm_selector({})

🎯 실전 응용

1. K번째 작은 원소 찾기

def quick_select(arr, k, left=0, right=None):
    """퀵 선택 알고리즘 - 평균 O(n)"""
    if right is None:
        right = len(arr) - 1
    
    if left == right:
        return arr[left]
    
    # 분할
    pivot_index = partition(arr, left, right)
    
    # k번째 원소 위치 확인
    if k == pivot_index:
        return arr[k]
    elif k < pivot_index:
        return quick_select(arr, k, left, pivot_index - 1)
    else:
        return quick_select(arr, k, pivot_index + 1, right)

# 테스트
arr = [3, 2, 1, 5, 6, 4]
k = 2  # 3번째 작은 원소 (0-indexed)
result = quick_select(arr.copy(), k)
print(f"배열: {arr}")
print(f"{k+1}번째 작은 원소: {result}")

2. 정렬된 배열 병합

def merge_k_sorted_arrays(arrays):
    """K개의 정렬된 배열 병합"""
    import heapq
    
    heap = []
    result = []
    
    # 각 배열의 첫 원소를 힙에 추가
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    
    while heap:
        val, arr_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        # 다음 원소 추가
        if elem_idx + 1 < len(arrays[arr_idx]):
            next_val = arrays[arr_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))
    
    return result

# 테스트
arrays = [
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9]
]
merged = merge_k_sorted_arrays(arrays)
print(f"병합 결과: {merged}")

3. 외부 정렬 (External Sort)

class ExternalSort:
    """대용량 파일 정렬 시뮬레이션"""
    
    def __init__(self, chunk_size=100):
        self.chunk_size = chunk_size
    
    def sort_large_file(self, data):
        """외부 정렬 시뮬레이션"""
        chunks = []
        
        # 1. 데이터를 청크로 분할하고 정렬
        for i in range(0, len(data), self.chunk_size):
            chunk = data[i:i + self.chunk_size]
            chunk.sort()  # 각 청크를 메모리에서 정렬
            chunks.append(chunk)
        
        print(f"총 {len(chunks)}개의 청크 생성")
        
        # 2. K-way 병합
        result = self.k_way_merge(chunks)
        
        return result
    
    def k_way_merge(self, chunks):
        """K-way 병합"""
        import heapq
        
        heap = []
        result = []
        
        # 각 청크의 첫 원소를 힙에 추가
        for i, chunk in enumerate(chunks):
            if chunk:
                heapq.heappush(heap, (chunk[0], i, 0))
        
        while heap:
            val, chunk_idx, elem_idx = heapq.heappop(heap)
            result.append(val)
            
            # 다음 원소 추가
            if elem_idx + 1 < len(chunks[chunk_idx]):
                next_val = chunks[chunk_idx][elem_idx + 1]
                heapq.heappush(heap, (next_val, chunk_idx, elem_idx + 1))
        
        return result

# 테스트
import random
data = [random.randint(1, 1000) for _ in range(500)]
external_sort = ExternalSort(chunk_size=100)
sorted_data = external_sort.sort_large_file(data.copy())
print(f"정렬 완료: {sorted_data[:10]}...")

📊 성능 비교

import time
import random

def compare_sorting_algorithms():
    """정렬 알고리즘 성능 비교"""
    
    sizes = [100, 1000, 5000]
    algorithms = {
        '버블 정렬': bubble_sort,
        '삽입 정렬': insertion_sort,
        '퀵 정렬': quick_sort_optimized,
        '병합 정렬': merge_sort,
        '힙 정렬': heap_sort,
        'Tim Sort': tim_sort,
        'Python 내장': sorted
    }
    
    print("정렬 알고리즘 성능 비교 (ms)")
    print("-" * 80)
    print(f"{'크기':<10}", end="")
    for name in algorithms.keys():
        print(f"{name:<12}", end="")
    print()
    print("-" * 80)
    
    for size in sizes:
        # 랜덤 데이터 생성
        data = [random.randint(1, 1000) for _ in range(size)]
        
        print(f"{size:<10}", end="")
        
        for name, func in algorithms.items():
            arr = data.copy()
            
            # 시간 측정
            start = time.perf_counter()
            if name == '퀵 정렬':
                func(arr)
            else:
                func(arr)
            end = time.perf_counter()
            
            elapsed = (end - start) * 1000  # ms
            
            # 버블 정렬은 큰 데이터에서 생략
            if name == '버블 정렬' and size > 1000:
                print(f"{'--':<12}", end="")
            else:
                print(f"{elapsed:<12.2f}", end="")
        
        print()

compare_sorting_algorithms()

🎯 핵심 정리

꼭 기억해야 할 5가지

1. 안정성: 동일한 값의 순서가 유지되는지
2. 제자리 정렬: 추가 메모리 사용 여부
3. 적응성: 입력 데이터 특성에 따른 성능 변화
4. 최악의 경우: 보장된 성능이 필요한지
5. 캐시 효율: 실제 성능은 캐시 활용도가 중요

실무 팁

• 대부분의 경우: 언어 내장 정렬 사용 (Tim Sort)
• 특수한 경우: 데이터 특성에 맞는 알고리즘 선택
• 부분 정렬: 전체 정렬이 필요 없으면 퀵 선택
• 외부 정렬: 메모리보다 큰 데이터는 분할 정렬

📚 추가 학습 자료

추천 문제

• LeetCode: Sort an Array, Kth Largest Element, Merge Intervals
• 프로그래머스: K번째수, 가장 큰 수, H-Index
• 백준: 2750(수 정렬하기), 10989(수 정렬하기 3), 1377(버블 소트)

🚀 다음 시간 예고

다음 포스트에서는 탐색 알고리즘을 다룹니다. 선형 탐색부터 이진 탐색, 그리고 고급 탐색 기법까지 알아보겠습니다!

---

📌 시리즈 네비게이션

순서	제목	링크
11	복잡도 분석: Big-O 표기법 완벽 마스터	← 이전 글
12	정렬 알고리즘: 버블 정렬부터 퀵 정렬까지 ✅	현재 글
13	탐색 알고리즘: 선형 탐색부터 이진 탐색까지	다음 글 →

📋 전체 시리즈 목차 보기

기초 이론편

1. CS 입문 ✅
2. 컴퓨터 구조 ✅
3. 이진수와 논리 게이트 ✅
4. 운영체제 기초 ✅
5. 네트워크 기초 ✅

자료구조편

1. 배열과 연결 리스트 ✅
2. 스택과 큐 ✅
3. 트리 구조 ✅
4. 그래프 ✅
5. 해시 테이블 ✅

알고리즘편

1. 복잡도 분석 ✅
2. 정렬 알고리즘 ✅
3. 탐색 알고리즘
4. 동적 계획법
5. 그리디와 분할정복

실무 응용편

1. 데이터베이스 이론
2. 소프트웨어 공학
3. 보안 기초
4. 분산 시스템
5. CS 종합과 면접 준비