정렬 알고리즘 (Sorting Algorithm)

개요

정렬 알고리즘(Sorting Algorithm)은 데이터 집합을 특정 기준(예: 오름차순 또는 내림차순)으로 정렬하는 알고리즘입니다. 정렬은 검색, 탐색, 데이터 분석 등의 다양한 컴퓨터 과학 분야에서 필수적인 작업입니다. 정렬 알고리즘은 크게 비교 기반 정렬(Comparison Sort) 과 비교 없는 정렬(Non-Comparison Sort) 로 나눌 수 있습니다.

---

1. 비교 기반 정렬 (Comparison Sort)

비교 기반 정렬 알고리즘은 요소 간의 크기를 비교하여 정렬하는 방식입니다. 대표적인 비교 기반 정렬 알고리즘에는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등이 있습니다.

1.1 버블 정렬 (Bubble Sort)

• 알고리즘 개요: 인접한 두 개의 원소를 비교하여 크기 순으로 정렬하는 방식
• 시간 복잡도: 평균 및 최악의 경우 $O(n^2)$, 최선의 경우 $O(n)$
• 특징: 구현이 간단하지만 비효율적

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:  # 인접한 요소 비교
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

---

1.2 선택 정렬 (Selection Sort)

• 알고리즘 개요: 리스트에서 최솟값을 찾아 앞쪽부터 하나씩 정렬하는 방식
• 시간 복잡도: 최선, 최악, 평균 모두 $O(n^2)$
• 특징: 비교 횟수가 많아 비효율적이지만 메모리 사용이 적음

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
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

---

1.3 삽입 정렬 (Insertion Sort)

• 알고리즘 개요: 이미 정렬된 부분에 새로운 원소를 적절한 위치에 삽입하는 방식
• 시간 복잡도: 평균 및 최악 $O(n^2)$, 최선 $O(n)$
• 특징: 대부분 정렬된 데이터에서 효율적이며, 적은 개수의 데이터를 정렬할 때 적합

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:  # key보다 큰 값은 한 칸씩 뒤로 이동
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

---

1.4 병합 정렬 (Merge Sort)

• 알고리즘 개요: 리스트를 반으로 나누어 각각 정렬한 후 합치는 방식
• 시간 복잡도: 최선, 평균, 최악 모두 $O(n\log n)$
• 특징: 안정 정렬이며, 메모리 사용량이 큼

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

---

1.5 퀵 정렬 (Quick Sort)

• 알고리즘 개요: 피벗을 기준으로 작은 값과 큰 값으로 나누어 정렬하는 방식
• 시간 복잡도: 평균 및 최선 $O(n\log n)$, 최악 $O(n^2)$
• 특징: 대부분의 경우 병합 정렬보다 빠름

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)

---

1.6 힙 정렬 (Heap Sort)

• 알고리즘 개요: 힙(완전 이진 트리 구조)을 이용한 정렬 방식
• 시간 복잡도: 최선, 평균, 최악 모두 $O(n\log n)$
• 특징: 안정 정렬이 아니며, 추가 메모리 사용이 적음

import heapq

def heap_sort(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

---

1.7 팀 정렬 (Timsort) - O(N log N)

• 알고리즘 개요: 삽입 정렬 + 병합 정렬(Merge Sort) 을 결합한 정렬 알고리즘
• 시간 복잡도: 최선 O(N), 평균 및 최악 O(N log N)
• 특징: 안정 정렬(Stable), 데이터가 부분적으로 정렬된 경우 효율적
• 사용 사례: Python의 sorted(), Java의 Arrays.sort(), Android의 정렬 메서드 등에 사용

📌 알고리즘 과정

1. 배열을 작은 크기의 "Run" (기본적으로 32~64개 요소) 단위로 나누고, 각 Run을 삽입 정렬을 이용해 정렬
2. 정렬된 Run을 병합 정렬(Merge Sort) 을 사용하여 병합
3. Galloping Mode (일반 병합 정렬보다 빠르게 동작하는 최적화된 병합 기법) 사용
4. 모든 Run이 병합되면 정렬 완료

📌 팀 정렬 코드 구현 (Python)

def insertion_sort(arr, left, right):
    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(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

def tim_sort(arr):
    RUN = 32  # 기본 Run 크기 설정
    n = len(arr)

    # Step 1: 작은 크기의 부분을 삽입 정렬
    for i in range(0, n, RUN):
        insertion_sort(arr, i, min((i+31), (n-1)))

    # Step 2: 병합 정렬을 활용하여 전체 정렬
    size = RUN
    while size < n:
        for left in range(0, n, size * 2):
            mid = left + size - 1
            right = min((left + 2 * size - 1), (n-1))
            if mid < right:
                merge(arr, left, mid, right)
        size *= 2

    return arr

팀 정렬 (Timsort) 주요 특징

✅ 안정 정렬 (Stable)
✅ 최적화된 정렬 방식으로 대부분의 데이터에서 빠름
✅ 최선의 경우 O(N), 일반적인 경우 O(N log N)
✅ Python, Java 등에서 기본 정렬 알고리즘으로 사용됨

---

2. 비교 없는 정렬 (Non-Comparison Sort)

비교 없이 정렬하는 방식으로, 특정 조건에서 매우 빠르게 동작합니다. 대표적인 알고리즘은 계수 정렬, 기수 정렬, 버킷 정렬이 있습니다.

2.1 계수 정렬 (Counting Sort)

• 알고리즘 개요: 입력값의 범위가 제한적일 때, 개수를 세어 정렬하는 방식
• 시간 복잡도: $O(n + k)$ (k는 최댓값)
• 특징: 비교 기반이 아니라 특정 조건에서만 사용할 수 있음

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])

    return sorted_arr

---

2.2 기수 정렬 (Radix Sort)

• 알고리즘 개요: 자리수별로 정렬하는 방식
• 시간 복잡도: $O(nk)$ (k는 자릿수)
• 특징: 정수 정렬에 적합하며, 비교 기반 정렬보다 빠름

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // 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]

---

이처럼 정렬 알고리즘은 다양한 방식으로 구현될 수 있으며, 데이터의 특성과 정렬 요구사항에 따라 적절한 알고리즘을 선택하는 것이 중요합니다. 🚀