정렬 알고리즘(Sorting Algorithms)이란?

정렬 알고리즘은 데이터를 특정 기준에 따라 순서를 맞추어 나열하는 알고리즘이다.
주로 숫자나 문자를 오름차순 또는 내림차순으로 정렬할 때 사용 됨
자료구조와 알고리즘 분야에서 기초적이면서도 매우 중요한 개념

---

1. 버블 정렬(Bubble Sort)

가장 간단한 정렬 방법 중 하나로, 인접한 두 원소를 비교하며 큰 값(또는 작은 값)을 계속 뒤로 보내면서 정렬

• 시간 복잡도: 최선 $O(N)$, 평균 및 최악 $O(N^2)$
• 공간 복잡도: $O(1)$
• 특징: 이해하기 쉽지만 성능이 좋지 않아 실제로는 거의 사용되지 않음

동작 과정

• 인접한 원소 두 개씩 비교하여 순서를 바꿈
• 배열 끝까지 반복하면 가장 큰(또는 작은) 원소가 맨 뒤로 이동
• 위 과정을 반복해 정렬을 완료

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

print(bubble_sort([4, 3, 5, 1, 2]))

---

2. 선택 정렬(Selection Sort)

매번 가장 작은(또는 가장 큰) 원소를 찾아 맨 앞으로 보내는 방식으로 정렬

• 시간 복잡도: 최선, 평균, 최악 모두 $O(N^2)$
• 공간 복잡도: $O(1)$
• 특징: 간단하지만 비효율적

동작 과정

• 전체 배열에서 가장 작은 원소를 찾아 첫 번째 위치와 교환
• 두 번째 위치부터 이 과정을 반복하여 전체를 정렬

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

print(selection_sort([4, 3, 5, 1, 2]))

---

3. 삽입 정렬(Insertion Sort)

배열의 각 원소를 이미 정렬된 부분에 삽입하는 방식

• 시간 복잡도: 최선 $O(N)$, 평균 및 최악 $O(N^2)$
• 공간 복잡도: $O(1)$
• 특징: 데이터가 어느 정도 정렬되어 있을 때 매우 효율적

동작 과정

• 첫 번째 원소를 정렬된 부분으로 간주
• 두 번째 원소부터 정렬된 부분 내 적절한 위치를 찾아 삽입
• 전체 원소를 대상으로 반복

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:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([4, 3, 5, 1, 2]))

---

4. 병합 정렬(Merge Sort)

배열을 절반씩 나누어 각각 정렬한 후 병합하는 방식으로, 분할 정복(Divide and Conquer)을 사용합니다.

• 시간 복잡도: 최선, 평균, 최악 모두 $O(N log N)$
• 공간 복잡도: $O(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

print(merge_sort([4, 3, 5, 1, 2]))

---

5. 퀵 정렬(Quick Sort)

기준점(pivot)을 정해 기준보다 작은 값과 큰 값을 나누어 정렬하는 방법

• 시간 복잡도: 최선, 평균 $O(N log N)$, 최악 $O(N^2)$
• 공간 복잡도: $O(log N)$
• 특징: 일반적으로 매우 빠르지만 피벗 선택에 따라 성능이 달라진다.

동작 과정

• 배열에서 피벗을 선정(첫 번째, 마지막, 중앙값 등)
• 피벗 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 배치
• 나뉜 부분에 대해 반복하여 정렬을 완료

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)

print(quick_sort([4, 3, 5, 1, 2]))

---

6. 힙 정렬(Heap Sort)

힙 자료구조를 이용하여 정렬하는 알고리즘

• 시간 복잡도: 최선, 평균, 최악 모두 $O(N log N)$
• 공간 복잡도: $O(1)$
• 특징: 성능이 안정적이며 추가 메모리 공간을 거의 사용하지 않음

동작 과정

• 배열을 힙(heap) 형태로 구성(heapify)
• 힙에서 루트 원소(최대 또는 최소)를 하나씩 꺼내어 배열 뒤에서부터 채움
• 힙을 재구성하며 반복적으로 진행

import heapq

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

print(heap_sort([4, 3, 5, 1, 2]))

# 힙 정렬(Heap Sort) 내부 동작 코드 예시

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

    # 루트가 최대가 아니라면 교환 후 하위 트리 heapify
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        print(f"heapify: swapped {arr[i]} and {arr[largest]}, array: {arr}")
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 최대 힙(max heap) 만들기
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
        print(f"build max-heap step: {arr}")

    print(f"Max heap constructed: {arr}")

    # 힙에서 요소를 하나씩 추출하며 정렬
    for i in range(n - 1, 0, -1):
        # 현재 루트(최대값)와 마지막 원소 교환
        arr[0], arr[i] = arr[i], arr[0]
        print(f"Swap root with index {i}: {arr}")
        
        # 힙 크기를 줄이고 다시 heapify
        heapify(arr, i, 0)
        print(f"Heap after removing max element: {arr}")

    return arr

# 테스트 코드
arr = [4, 3, 5, 1, 2]
sorted_arr = heap_sort(arr)
print(f"Sorted array: {sorted_arr}")

---

정렬 알고리즘 특징 비교

알고리즘	최선	평균	최악	공간복잡도
버블 정렬	$O(N)$	$O(N^2)$	$O(N^2)$	$O(1)$
선택 정렬	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$
삽입 정렬	$O(N)$	$O(N^2)$	$O(N^2)$	$O(1)$
병합 정렬	$O(N log N)$	$O(N log N)$	$O(N log N)$	$O(N)$
퀵 정렬	$O(N log N)$	$O(N log N)$	$O(N^2)$	$O(log N)$
힙 정렬	$O(N log N)$	$O(N log N)$	$O(N log N)$	$O(1)$

---

정리

정렬 알고리즘은 각각의 상황과 데이터 특성에 따라 선택하는 것이 중요하다.

• 데이터가 거의 정렬되어 있으면 삽입 정렬이 효율적
• 일반적인 경우 빠른 속도를 원하면 퀵 정렬을 고려
• 안정적이고 일관된 성능이 필요하면 병합 정렬이나 힙 정렬이 적합