[TIL] 101. [분할 정복, 정렬] 퀵 정렬, 병합 정렬

키워드

• 분할 정복
• 퀵 정렬
• 병합 정렬

분할 정복

• 복잡하거나 큰 문제를 작은 하위 문제로 나누어 푸는 방법
• 문제를 나누어 병렬적으로 해결 가능(단, 문제해결을 위해 함수가 재귀적으로 호출될 수 있으므로 메모리 사용량 증가)
• 분할(Divide) : 문제를 작게 작게 나누는 과정
• 정복(Conquer) : 작게 나눈 문제를 하나씩 return 하여 정복(특정값을 도출)
• 먼저 Divide를 한 후 그의 역순으로 작은 문제부터 하나하나 정복해서 최종 결과값을 도출
• 단, 과연 이 문제를 분할 정복으로 해결하는 것이 더 효율적인 것이도 생각해볼 필요가 있다!
• 아래는 재귀와 분할 정복의 차이(분할 정복은 보통 재귀함수를 활용)

[정렬, 분할정복] 퀵 정렬(Quick Sort)

• 피벗(pivot)이라는 값을 특정지어주고(보통 배열의 맨 앞 혹은 맨 뒤 이용)
  해당값의 왼쪽엔 피벗보다 작은 값, 오른쪽엔 피벗보다 큰 값을 두며 반복 호출
• 평균적으로 O(nlogn)이지만, 최악의 경우 O(n^2)
• 불안정 정렬로서 중복되는 값이 존재할 때, 중복값에 대한 순서를 보장할 수 없다.(반대로 중복값의 순서가 유지되는 건 안정 정렬)
• 성능이 우수하지만, 성능의 편차가 크고(시간복잡도 상) 피벗 설정을 다루기 어려운 점으로 실무에서는 활용도가 낮다.

def quick_sort(li):
    if len(li) <= 1:
        return li
    else:
        pivot = li[0]
        less = [left for left in li[1:] if left <= pivot]
        great = [right for right in li[1:] if right > pivot]

        return quick_sort(less) + [pivot] + quick_sort(great)

[정렬, 분할정복] 병합정렬(Merge Sort)

• 주어질 배열을 원소가 하나밖에 남지 않을 때까지 계속 둘로 쪼갠 후 다시 크기 순으로 재배열하면서 원래 크기의 배열로 결합

 

• 분할 파트 : 주어진 배열을 더 작은 배열로 나누는 과정, 더 이상 분할 할 수 없는 경우 중지

def merge_sort(li):
    if len(li) <= 1:
        return li
    else:
        mid = len(li) // 2  ## 주어진 배열의 가운데 인덱스를 설정하고 왼쪽과 오른쪽으로 배열 분할
        left = merge_sort(li[:mid])
        right = merge_sort(li[mid:])

        return merge(left, right)

 

• 결합 파트 : 병합 정렬에서 핵심이 되는 과정으로, 결합 하면서 정렬도 함께 진행된다.

def merge(left, right):
    merged_arr = [] # 결합을 위한 빈 리스트 생성
    i = j = 0 # 인덱스값 초기화를 위한 설정

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged_arr.append(left[i])
            i += 1
        else:
            merged_arr.append(right[j])
            j += 1

    merged_arr += left[i:]
    merged_arr += right[j:] # while문에서 처리되지 않은 값들을 더해주는 과정

    return merged_arr

---

개인적으로 기본 정렬(버블, 삽입, 선택) 그리고 분할 정복을 활용한 정렬(퀵, 병합) 중 병합 정렬의 알고리즘이 참 신기한 것 같다.
개념 자체는 간단하지만 병합정렬의 핵심인 merge 부분에서 sorting이 됨과 동시에 merge가 되는 알고리즘에서 많이 배울 수 있었다.