05_sorting.py - Examples

  1"""
  2정렬 알고리즘 (Sorting Algorithms)
  3Sorting Algorithms Comparison
  4
  5다양한 정렬 알고리즘의 구현과 비교입니다.
  6"""
  7
  8import random
  9import time
 10from typing import List
 11
 12
 13# =============================================================================
 14# 1. 버블 정렬 (Bubble Sort)
 15# =============================================================================
 16def bubble_sort(arr: List[int]) -> List[int]:
 17    """
 18    버블 정렬
 19    시간: O(n²), 공간: O(1), 안정 정렬
 20    """
 21    arr = arr.copy()
 22    n = len(arr)
 23
 24    for i in range(n):
 25        swapped = False
 26        for j in range(0, n - i - 1):
 27            if arr[j] > arr[j + 1]:
 28                arr[j], arr[j + 1] = arr[j + 1], arr[j]
 29                swapped = True
 30        if not swapped:
 31            break
 32
 33    return arr
 34
 35
 36# =============================================================================
 37# 2. 선택 정렬 (Selection Sort)
 38# =============================================================================
 39def selection_sort(arr: List[int]) -> List[int]:
 40    """
 41    선택 정렬
 42    시간: O(n²), 공간: O(1), 불안정 정렬
 43    """
 44    arr = arr.copy()
 45    n = len(arr)
 46
 47    for i in range(n):
 48        min_idx = i
 49        for j in range(i + 1, n):
 50            if arr[j] < arr[min_idx]:
 51                min_idx = j
 52        arr[i], arr[min_idx] = arr[min_idx], arr[i]
 53
 54    return arr
 55
 56
 57# =============================================================================
 58# 3. 삽입 정렬 (Insertion Sort)
 59# =============================================================================
 60def insertion_sort(arr: List[int]) -> List[int]:
 61    """
 62    삽입 정렬
 63    시간: O(n²), 최선 O(n), 공간: O(1), 안정 정렬
 64    거의 정렬된 데이터에 효율적
 65    """
 66    arr = arr.copy()
 67    n = len(arr)
 68
 69    for i in range(1, n):
 70        key = arr[i]
 71        j = i - 1
 72        while j >= 0 and arr[j] > key:
 73            arr[j + 1] = arr[j]
 74            j -= 1
 75        arr[j + 1] = key
 76
 77    return arr
 78
 79
 80# =============================================================================
 81# 4. 병합 정렬 (Merge Sort)
 82# =============================================================================
 83def merge_sort(arr: List[int]) -> List[int]:
 84    """
 85    병합 정렬
 86    시간: O(n log n), 공간: O(n), 안정 정렬
 87    """
 88    if len(arr) <= 1:
 89        return arr
 90
 91    mid = len(arr) // 2
 92    left = merge_sort(arr[:mid])
 93    right = merge_sort(arr[mid:])
 94
 95    return merge(left, right)
 96
 97
 98def merge(left: List[int], right: List[int]) -> List[int]:
 99    """두 정렬된 배열 병합"""
100    result = []
101    i = j = 0
102
103    while i < len(left) and j < len(right):
104        if left[i] <= right[j]:
105            result.append(left[i])
106            i += 1
107        else:
108            result.append(right[j])
109            j += 1
110
111    result.extend(left[i:])
112    result.extend(right[j:])
113    return result
114
115
116# =============================================================================
117# 5. 퀵 정렬 (Quick Sort)
118# =============================================================================
119def quick_sort(arr: List[int]) -> List[int]:
120    """
121    퀵 정렬
122    시간: 평균 O(n log n), 최악 O(n²), 공간: O(log n), 불안정 정렬
123    """
124    if len(arr) <= 1:
125        return arr
126
127    pivot = arr[len(arr) // 2]
128    left = [x for x in arr if x < pivot]
129    middle = [x for x in arr if x == pivot]
130    right = [x for x in arr if x > pivot]
131
132    return quick_sort(left) + middle + quick_sort(right)
133
134
135def quick_sort_inplace(arr: List[int], low: int = 0, high: int = None) -> List[int]:
136    """퀵 정렬 (in-place)"""
137    if high is None:
138        arr = arr.copy()
139        high = len(arr) - 1
140
141    if low < high:
142        pivot_idx = partition(arr, low, high)
143        quick_sort_inplace(arr, low, pivot_idx - 1)
144        quick_sort_inplace(arr, pivot_idx + 1, high)
145
146    return arr
147
148
149def partition(arr: List[int], low: int, high: int) -> int:
150    """파티션 (Lomuto scheme)"""
151    pivot = arr[high]
152    i = low - 1
153
154    for j in range(low, high):
155        if arr[j] <= pivot:
156            i += 1
157            arr[i], arr[j] = arr[j], arr[i]
158
159    arr[i + 1], arr[high] = arr[high], arr[i + 1]
160    return i + 1
161
162
163# =============================================================================
164# 6. 힙 정렬 (Heap Sort)
165# =============================================================================
166def heap_sort(arr: List[int]) -> List[int]:
167    """
168    힙 정렬
169    시간: O(n log n), 공간: O(1), 불안정 정렬
170    """
171    arr = arr.copy()
172    n = len(arr)
173
174    # 최대 힙 구성
175    for i in range(n // 2 - 1, -1, -1):
176        heapify(arr, n, i)
177
178    # 하나씩 추출
179    for i in range(n - 1, 0, -1):
180        arr[0], arr[i] = arr[i], arr[0]
181        heapify(arr, i, 0)
182
183    return arr
184
185
186def heapify(arr: List[int], n: int, i: int):
187    """최대 힙 속성 유지"""
188    largest = i
189    left = 2 * i + 1
190    right = 2 * i + 2
191
192    if left < n and arr[left] > arr[largest]:
193        largest = left
194    if right < n and arr[right] > arr[largest]:
195        largest = right
196
197    if largest != i:
198        arr[i], arr[largest] = arr[largest], arr[i]
199        heapify(arr, n, largest)
200
201
202# =============================================================================
203# 7. 계수 정렬 (Counting Sort)
204# =============================================================================
205def counting_sort(arr: List[int]) -> List[int]:
206    """
207    계수 정렬
208    시간: O(n + k), 공간: O(k), 안정 정렬
209    k = 최댓값 - 최솟값 + 1
210    정수 범위가 작을 때 효율적
211    """
212    if not arr:
213        return []
214
215    min_val, max_val = min(arr), max(arr)
216    range_val = max_val - min_val + 1
217
218    count = [0] * range_val
219    output = [0] * len(arr)
220
221    # 카운트
222    for num in arr:
223        count[num - min_val] += 1
224
225    # 누적
226    for i in range(1, range_val):
227        count[i] += count[i - 1]
228
229    # 역순으로 배치 (안정성 유지)
230    for i in range(len(arr) - 1, -1, -1):
231        num = arr[i]
232        count[num - min_val] -= 1
233        output[count[num - min_val]] = num
234
235    return output
236
237
238# =============================================================================
239# 8. 기수 정렬 (Radix Sort)
240# =============================================================================
241def radix_sort(arr: List[int]) -> List[int]:
242    """
243    기수 정렬 (LSD)
244    시간: O(d * (n + k)), 공간: O(n + k)
245    d = 자릿수, k = 기수 (보통 10)
246    음수 미지원 버전
247    """
248    if not arr or min(arr) < 0:
249        return sorted(arr)  # 음수 포함 시 기본 정렬
250
251    max_val = max(arr)
252
253    exp = 1
254    while max_val // exp > 0:
255        arr = counting_sort_by_digit(arr, exp)
256        exp *= 10
257
258    return arr
259
260
261def counting_sort_by_digit(arr: List[int], exp: int) -> List[int]:
262    """특정 자릿수 기준 계수 정렬"""
263    n = len(arr)
264    output = [0] * n
265    count = [0] * 10
266
267    for num in arr:
268        digit = (num // exp) % 10
269        count[digit] += 1
270
271    for i in range(1, 10):
272        count[i] += count[i - 1]
273
274    for i in range(n - 1, -1, -1):
275        digit = (arr[i] // exp) % 10
276        count[digit] -= 1
277        output[count[digit]] = arr[i]
278
279    return output
280
281
282# =============================================================================
283# 성능 비교
284# =============================================================================
285def benchmark_sorts(size: int = 1000):
286    """정렬 알고리즘 성능 비교"""
287    arr = [random.randint(0, 10000) for _ in range(size)]
288
289    algorithms = [
290        ("Bubble Sort", bubble_sort, size <= 1000),
291        ("Selection Sort", selection_sort, size <= 1000),
292        ("Insertion Sort", insertion_sort, size <= 1000),
293        ("Merge Sort", merge_sort, True),
294        ("Quick Sort", quick_sort, True),
295        ("Heap Sort", heap_sort, True),
296        ("Counting Sort", counting_sort, True),
297        ("Radix Sort", radix_sort, True),
298        ("Python sorted()", sorted, True),
299    ]
300
301    print(f"\n배열 크기: {size}")
302    print("-" * 50)
303
304    for name, func, should_run in algorithms:
305        if should_run:
306            test_arr = arr.copy()
307            start = time.perf_counter()
308            result = func(test_arr)
309            elapsed = time.perf_counter() - start
310            print(f"{name:20s}: {elapsed * 1000:8.3f} ms")
311        else:
312            print(f"{name:20s}: (크기 초과로 스킵)")
313
314
315# =============================================================================
316# 테스트
317# =============================================================================
318def main():
319    print("=" * 60)
320    print("정렬 알고리즘 (Sorting Algorithms)")
321    print("=" * 60)
322
323    # 테스트 배열
324    arr = [64, 34, 25, 12, 22, 11, 90]
325    print(f"\n원본 배열: {arr}")
326    print("-" * 40)
327
328    # 각 알고리즘 테스트
329    algorithms = [
330        ("버블 정렬", bubble_sort),
331        ("선택 정렬", selection_sort),
332        ("삽입 정렬", insertion_sort),
333        ("병합 정렬", merge_sort),
334        ("퀵 정렬", quick_sort),
335        ("힙 정렬", heap_sort),
336        ("계수 정렬", counting_sort),
337        ("기수 정렬", radix_sort),
338    ]
339
340    for name, func in algorithms:
341        result = func(arr.copy())
342        print(f"{name}: {result}")
343
344    # 성능 비교
345    print("\n" + "=" * 60)
346    print("성능 비교 (Performance Benchmark)")
347    print("=" * 60)
348
349    for size in [100, 1000, 5000]:
350        benchmark_sorts(size)
351
352    # 정렬 알고리즘 비교표
353    print("\n" + "=" * 60)
354    print("정렬 알고리즘 비교")
355    print("=" * 60)
356    print("""
357    | 알고리즘     | 평균      | 최악      | 공간   | 안정성 | 특징                |
358    |-------------|----------|----------|--------|-------|---------------------|
359    | 버블 정렬    | O(n²)    | O(n²)    | O(1)   | 안정  | 단순, 교육용         |
360    | 선택 정렬    | O(n²)    | O(n²)    | O(1)   | 불안정| 단순, 교환 횟수 적음  |
361    | 삽입 정렬    | O(n²)    | O(n²)    | O(1)   | 안정  | 거의 정렬된 데이터에 좋음|
362    | 병합 정렬    | O(nlogn) | O(nlogn) | O(n)   | 안정  | 일정한 성능          |
363    | 퀵 정렬      | O(nlogn) | O(n²)    | O(logn)| 불안정| 평균적으로 가장 빠름  |
364    | 힙 정렬      | O(nlogn) | O(nlogn) | O(1)   | 불안정| in-place, 일정한 성능|
365    | 계수 정렬    | O(n+k)   | O(n+k)   | O(k)   | 안정  | 정수, 범위 작을 때    |
366    | 기수 정렬    | O(d(n+k))| O(d(n+k))| O(n+k) | 안정  | 자릿수 기반           |
367
368    실무 선택 가이드:
369    - 일반적인 경우: 퀵 정렬 또는 언어 내장 정렬
370    - 안정성 필요: 병합 정렬
371    - 메모리 제한: 힙 정렬
372    - 거의 정렬됨: 삽입 정렬
373    - 정수 + 범위 작음: 계수/기수 정렬
374    """)
375
376
377if __name__ == "__main__":
378    main()