[Algorithm] 정렬 알고리즘 시간 복잡도 비교 및 구현

정렬 알고리즘은 데이터 정렬에 자주 사용되는 다양한 방법들로, 각각의 알고리즘은 고유한 특성과 성능을 가지고 있다. 이번 포스트에서는 버블 정렬, 선택 정렬, 삽입 정렬, 기수 정렬, 병합 정렬, 퀵 정렬, 힙 정렬의 최소, 최대, 평균 시간 복잡도를 비교하고, 각 알고리즘이 stable sort와 In-place sort인지 여부를 표로 정리하여 비교한다.

시간 복잡도 비교

정렬 알고리즘의 시간 복잡도는 최악, 최선, 평균의 세 가지 측면에서 평가할 수 있다. 아래 표는 각 알고리즘의 시간 복잡도를 요약한 것이다.

정렬 알고리즘	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도	Stable	In-place
버블 정렬	O(n)	O(n^2)	O(n^2)	O	O
선택 정렬	O(n^2)	O(n^2)	O(n^2)	X	O
삽입 정렬	O(n)	O(n^2)	O(n^2)	O	O
기수 정렬	O(nk)	O(nk)	O(nk)	O	X
병합 정렬	O(n log n)	O(n log n)	O(n log n)	O	X
퀵 정렬	O(n log n)	O(n log n)	O(n^2)	X	O
힙 정렬	O(n log n)	O(n log n)	O(n log n)	X	O

각 알고리즘 설명

버블 정렬 (Bubble Sort)

• 특징: 인접한 두 요소를 비교하여 교환하는 방식으로 정렬한다.
• 장점: 구현이 간단하고, 이미 정렬된 배열에서는 최선의 성능(O(n))을 보인다.
• 단점: 일반적으로는 O(n^2)으로 느리다.
• Stable: O
• In-place: O

선택 정렬 (Selection Sort)

• 특징: 배열에서 가장 작은 요소를 찾아 첫 번째 요소와 교환하는 방식으로 정렬한다.
• 장점: 구현이 간단하다.
• 단점: 항상 O(n^2)로 비효율적이다.
• Stable: X
• In-place: O

삽입 정렬 (Insertion Sort)

• 특징: 배열의 요소를 하나씩 골라서 이미 정렬된 부분에 삽입하는 방식이다.
• 장점: 적은 요소에 대해서는 효율적이고, 거의 정렬된 배열에서는 O(n)이다.
• 단점: 일반적으로 O(n^2)으로 큰 배열에 비효율적이다.
• Stable: O
• In-place: O

기수 정렬 (Radix Sort)

• 특징: 자릿수별로 정렬하여 전체 정렬을 수행한다.
• 장점: O(nk)로 큰 숫자에 대해 효율적이다.
• 단점: k가 클 때 비효율적이고, 추가 메모리를 사용한다.
• Stable: O
• In-place: X

병합 정렬 (Merge Sort)

• 특징: 배열을 반으로 나누어 각각 정렬 후 병합한다.
• 장점: O(n log n)으로 항상 빠르다.
• 단점: 추가 메모리를 사용한다.
• Stable: O
• In-place: X

퀵 정렬 (Quick Sort)

• 특징: 피벗을 기준으로 작은 요소와 큰 요소를 분할하여 정렬한다.
• 장점: 평균적으로 O(n log n)으로 빠르다.
• 단점: 최악의 경우(피봇이 잘못 잡힐 때) O(n^2)으로 느리다.
• Stable: X
• In-place: O

힙 정렬 (Heap Sort)

• 특징: 최대/최소 힙을 사용하여 정렬한다.
• 장점: 항상 O(n log n)으로 안정적이다.
• 단점: 비교적 복잡하다.
• Stable: X
• In-place: O

버블 vs 선택 vs 삽입

• 거품 정렬: 일반적으로 셋 중 가장 느리다. 그러나 정렬된 배열의 경우, sorted의 값이 계속 true이기 때문에 시간이 매우 빨라진다.
• 선택 정렬: 배열의 상태와 상관 없이, 1번째로 작은 원소를 찾고, 2번째로 작은 원소를 찾고, ... 하는 과정을 거치기 때문에 어떠한 상황이던 동일한 시간을 보인다.
• 삽입 정렬: 일반적으로는 가장 빠르나, 값이 반대로 정렬되어 있는 경우 성능이 많이 떨어진다. 또한, 앞 배열에 값을 삽입하는 알고리즘의 특성상 이미 정렬된 배열에 추가적으로 값을 몇 개 추가하여 정렬하는 경우에 좋은 성능을 보인다.

각 정렬 알고리즘의 파이썬 구현

버블 정렬 (Bubble Sort)

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

선택 정렬 (Selection Sort)

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

삽입 정렬 (Insertion Sort)

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        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

기수 정렬 (Radix Sort)

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max1 = max(arr)
    exp = 1
    while max1 // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

병합 정렬 (Merge Sort)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

퀵 정렬 (Quick Sort)

def partition(arr, low, high):
    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(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
    return arr

힙 정렬 (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

    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