정렬 알고리즘 (Sorting Algorithms)

정렬 알고리즘은 주어진 배열이나 리스트의 원소들을 비교 연산자에 따라 재배열하는 데 사용된다. 비교 연산자는 데이터 구조 내에서 원소의 새로운 순서를 결정한다. 예를 들어, 숫자 순서(numerical order)는 일반적으로 사용되는 방식이며, 사전식 순서(lexicographical order) 역시 흔히 쓰인다.

정렬 알고리즘에는 여러 종류가 있으며, 대표적으로 퀵 정렬(Quick Sort), 버블 정렬(Bubble Sort), 병합 정렬(Merge Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort), 힙 정렬(Heap Sort) 등이 있다. 각 알고리즘은 특성이 다르고, 데이터 크기나 상황에 따라 적합한 방식이 다르다.

---

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 원소들을 반복적으로 비교하여 잘못된 순서일 경우 서로 교환하는 방식으로 동작한다. 가장 큰 원소가 반복(iteration)을 거치며 점점 뒤로 이동하는 모습이 물방울이 위로 올라가는 것과 비슷하다. 단순하다는 장점이 있지만, 평균 및 최악의 경우 시간 복잡도가 O(n²)이므로 대규모 데이터셋에는 적합하지 않다.

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

print(bubble_sort([64, 25, 12, 22, 11]))

---

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복(Divide and Conquer) 방식을 따르는 정렬 알고리즘이다. 리스트를 재귀적으로 분할한 뒤, 다시 합치면서 정렬을 수행한다. 최선, 평균, 최악 모두 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

print(merge_sort([64, 25, 12, 22, 11]))

---

삽입 정렬 (Insertion Sort)

삽입 정렬은 리스트를 왼쪽에서 오른쪽으로 순회하면서, 각 원소를 이미 정렬된 부분에 적절한 위치에 삽입하는 방식이다. 작은 데이터셋이나 부분적으로 정렬된 데이터에서 효율적이다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([64, 25, 12, 22, 11]))

---

퀵 정렬 (Quick Sort)

퀵 정렬은 피벗(pivot)을 기준으로 작은 값과 큰 값으로 나누어 재귀적으로 정렬한다. 평균 시간 복잡도는 O(n log n)이지만, 최악의 경우 O(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([64, 25, 12, 22, 11]))

---

선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 가장 작은 원소를 찾아 맨 앞 원소와 교환하고, 그 다음 작은 원소를 찾아 두 번째 원소와 교환하는 방식으로 동작한다. 시간 복잡도는 O(n²)이다.

def selection_sort(arr):
    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

print(selection_sort([64, 25, 12, 22, 11]))

---

힙 정렬 (Heap Sort)

힙 정렬은 이진 힙(binary heap)을 이용하는 정렬 방식이다. 최대 힙을 구성한 뒤, 루트(가장 큰 값)를 꺼내 배열 끝에 배치하고 다시 힙을 재구성한다. 항상 O(n log n) 복잡도를 가진다.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

print(heap_sort([64, 25, 12, 22, 11]))

---

마무리

정렬 알고리즘은 데이터 구조와 알고리즘의 기본 중 기본이다. 실제 코딩 테스트나 실무에서 상황에 따라 적절한 알고리즘을 선택할 수 있어야 한다. 단순한 정렬 방식인 버블/삽입/선택 정렬은 개념 이해에 좋고, 병합/퀵/힙 정렬은 대규모 데이터에서 강력한 성능을 발휘한다.