[Python] 알고리즘 개념19 - 정렬 알고리즘 (퀵 정렬, 병합 정렬, 힙 정렬)

 

 

🚀 1. 정렬 알고리즘이란?

**정렬(Sorting)**은 데이터를 일정한 순서대로 재배열하는 과정이에요.

 

💡 정렬이 중요한 이유

• 📂 데이터 검색을 빠르게 할 수 있어요. (예: 이진 탐색)
• 📊 데이터를 분석하기 편리해요. (예: 최댓값, 최솟값 찾기)
• ⚡ 알고리즘의 성능을 높일 수 있어요. (예: 그리디, 동적 계획법 활용)

 

📌 정렬 알고리즘의 주요 목표

1. 시간 복잡도를 최소화하여 빠르게 정렬하는 것.
2. 메모리 사용량을 줄여 효율적인 정렬을 수행하는 것.
3. 데이터의 기존 순서를 유지하는지(안정 정렬) 여부를 고려하는 것.

➡ 정렬 알고리즘은 다양한 방식이 있으며, 상황에 따라 적절한 알고리즘을 선택해야 해요!

---

 

 

🚀 2. 대표적인 정렬 알고리즘 비교

 

📌 정렬 알고리즘별 성능 비교

정렬 알고리즘 / 평균 시간 복잡도 / 최악 시간 복잡도 / 공간 복잡도 / 안정 정렬

퀵 정렬	O(n log n)	O(n²)	O(log n) (재귀 호출)	❌ (피벗 선택에 따라 다름)
병합 정렬	O(n log n)	O(n log n)	O(n)	✅
힙 정렬	O(n log n)	O(n log n)	O(1)	❌

➡ 퀵 정렬, 병합 정렬, 힙 정렬은 모두 O(n log n)의 성능을 가지지만, 각각의 특성이 달라요!

---

 

 

🚀 3. 퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘의 대표적인 예제예요.

 

💡 퀵 정렬이 빠른 이유

• 불필요한 비교를 최소화하기 위해 피벗(Pivot)을 기준으로 분할
• 정렬이 끝난 후에는 추가적인 병합 과정이 필요하지 않음

 

📌 퀵 정렬이 적합한 경우

• 대부분의 경우 평균 O(n log n)의 성능을 가지므로 빠르게 정렬할 때 사용
• 추가적인 메모리 공간을 거의 사용하지 않음

 

⚠ 퀵 정렬이 비효율적인 경우

• 최악의 경우(이미 정렬된 배열에서 피벗을 잘못 선택)에는 O(n²)까지 성능이 저하될 수 있음
• 이런 경우, **랜덤 피벗 선택(Randomized Quick Sort)**을 사용하면 해결 가능

퀵 정렬은 기준(Pivot)을 정하고, 이를 기준으로 작은 값과 큰 값으로 나누어 정렬하는 알고리즘이에요.

 

📌 퀵 정렬의 핵심 개념

1. 피벗(Pivot) 선택: 정렬 기준이 되는 값을 선택해요.
2. 분할(Divide): 피벗을 기준으로 작은 값과 큰 값으로 나눠요.
3. 정복(Conquer): 나뉜 부분을 재귀적으로 정렬해요.

 

💡 Python 코드 구현

def quick_sort(arr):
    """
    퀵 정렬(Quick Sort)
    - 피벗을 기준으로 작은 값과 큰 값으로 나누어 정렬하는 알고리즘
    - 평균적으로 O(n log n)의 성능을 가지며 매우 빠름
    """
    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)

arr = [5, 3, 8, 6, 2, 7, 4, 1]
print(quick_sort(arr))  # 출력: [1, 2, 3, 4, 5, 6, 7, 8]

➡ 퀵 정렬은 평균적으로 O(n log n) 성능을 가지며, 매우 빠른 정렬 알고리즘이에요!

 

---

 

 

🚀 4. 병합 정렬(Merge Sort)

병합 정렬은 안정적인 정렬 알고리즘으로, 항상 O(n log n)의 성능을 보장하는 장점이 있어요.

 

💡 병합 정렬이 강력한 이유

• 입력 데이터의 상태와 관계없이 O(n log n)을 보장
• 데이터를 나눈 후 다시 병합하는 방식이므로, 안정 정렬(Stable Sort)이다.
• 배열뿐만 아니라 연결 리스트(Linked List) 정렬에도 적합

 

📌 병합 정렬이 적합한 경우

• 데이터 크기가 클 때도 일정한 성능을 보장해야 할 경우
• 외부 정렬(External Sorting)에서 활용 (예: 매우 큰 파일을 여러 개로 나누어 정렬 후 합치는 방식)

 

⚠ 병합 정렬의 단점

• 추가적인 메모리 공간(O(n))이 필요하므로, 공간 효율성이 떨어질 수 있음
• 리스트를 병합하는 과정에서 비교 연산이 많이 발생할 수 있음

 

병합 정렬은 배열을 반으로 나누고, 각각을 정렬한 후 병합하는 방식의 정렬 알고리즘이에요.

 

📌 병합 정렬의 핵심 개념

1. 분할(Divide): 배열을 반으로 나눠요.
2. 정복(Conquer): 나눈 배열을 각각 정렬해요.
3. 병합(Merge): 정렬된 배열을 합쳐요.

 

💡 Python 코드 구현

def merge_sort(arr):
    """
    병합 정렬(Merge Sort)
    - 배열을 반으로 나누고 각각 정렬한 후 병합하는 정렬 알고리즘
    - 항상 O(n log n)의 시간복잡도를 보장하며, 안정 정렬(stable sort)이다.
    """
    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):
    sorted_arr = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    return sorted_arr

arr = [5, 3, 8, 6, 2, 7, 4, 1]
print(merge_sort(arr))  # 출력: [1, 2, 3, 4, 5, 6, 7, 8]

➡ 병합 정렬은 O(n log n)의 시간 복잡도를 유지하는 안정적인 정렬 방법이에요!

---

 

 

🚀 5. 힙 정렬(Heap Sort)

힙 정렬은 완전 이진 트리(Complete Binary Tree)의 구조를 활용하는 정렬 알고리즘이에요.

 

💡 힙 정렬이 강력한 이유

• 추가적인 메모리 공간이 거의 필요하지 않음 (O(1) 공간 복잡도)
• 항상 O(n log n)의 성능을 유지함 (최악의 경우에도 보장됨)
• 우선순위 큐(Priority Queue) 구현에 사용됨

 

📌 힙 정렬이 적합한 경우

• 추가적인 메모리 사용이 제한된 환경에서 정렬해야 할 때
• 실시간 데이터 정렬이 필요한 경우 (예: 스트리밍 데이터 처리)

 

⚠ 힙 정렬의 단점

• 비교적 느린 실행 속도: 퀵 정렬보다 실제 연산 속도가 느릴 수 있음
• 불안정 정렬(Unstable Sort): 동일한 값이 입력될 경우 기존 순서를 유지하지 않음

 

힙 정렬은 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 활용하여 정렬하는 알고리즘이에요.

 

📌 힙 정렬의 핵심 개념

1. 힙(Heap) 생성: 배열을 최대 힙 또는 최소 힙 구조로 변환해요.
2. 정렬 수행: 힙에서 하나씩 요소를 꺼내 정렬해요.

 

💡 Python 코드 구현

import heapq

def heap_sort(arr):
    """
    힙 정렬(Heap Sort)
    - 최소 힙 또는 최대 힙을 활용한 정렬 알고리즘
    - 추가적인 메모리 사용이 적으며, O(n log n)의 시간 복잡도를 가진다.
    """
    heapq.heapify(arr)  # 주어진 배열을 최소 힙(min-heap)으로 변환  # 최소 힙 생성
    sorted_arr = []
    while arr:
        sorted_arr.append(heapq.heappop(arr))  # 힙에서 최소값을 하나씩 꺼내어 정렬
    return sorted_arr

arr = [5, 3, 8, 6, 2, 7, 4, 1]
print(heap_sort(arr))  # 출력: [1, 2, 3, 4, 5, 6, 7, 8]

➡ 힙 정렬은 O(n log n)의 시간 복잡도를 가지며, 추가 공간이 거의 필요하지 않아요!

---

 

 

✅ 마무리 정리

• 퀵 정렬(Quick Sort): 피벗을 기준으로 작은 값과 큰 값으로 나누는 정렬 (O(n log n), 불안정 정렬)
• 병합 정렬(Merge Sort): 배열을 나누고 병합하여 정렬하는 방법 (O(n log n), 안정 정렬)
• 힙 정렬(Heap Sort): 힙 구조를 활용한 정렬 방법 (O(n log n), 불안정 정렬)