시간복잡도 O(NlogN)정렬 알고리즘 알아보기 with Python

이전에 시간 복잡도 O(N^2)인 정렬 알고리즘들에 대해 포스팅했었는데요.

오늘은 시간 복잡도가 O(NlogN)인 정렬 알고리즘에 대해 알아보려 합니다!

시간복잡도가 O(NlogN)인 대표적인 정렬에는 퀵 정렬, 합병 정렬, 힙 정렬이 있습니다. 

 

1. 퀵 정렬

---

분할 정복(divide and conquer)기법을 사용한 정렬로, 평균적으로 아주 빠른 성능을 갖는 알고리즘입니다. 

 

정렬 방법

1. 주어진 리스트에서 하나의 원소를 고른다. (피벗)

2. 피벗을 기준으로 두 개의 파티션으로 분할한다.  파티션 1: 피벗보다 작은 원소,   파티션 2: 피벗보다 큰 원소

3. 분할된 파티션에 대해서도 리스트의 크기가 0 혹은 1이 될 때까지 1,2 과정을 반복한다. 

 

소스코드(파이썬)

def quick_sort(a: list) -> list:
    n = len(a)
    
    if n <= 1:
        return a
    
    pivot = a[-1]
    a_left = []
    a_right = []
    
    for i in range(0,n-1):
        if a[i] < pivot:
            a_left.append(a[i])
        else:
            a_right.append(a[i])
        
    return quick_sort(a_left) + [pivot] + quick_sort(a_right)

특징: 제자리 정렬 알고리즘 (정렬에 사용되는 추가적인 저장공간이 매우 작음), 불안정적인 정렬 (같은 값일 때 순서가 변할 수 있음)

 

 

2. 합병 정렬

---

퀵 정렬과 마찬가지로 분할 정복(divide and conquer)기법을 사용한 정렬입니다. 퀵 정렬과의 차이점은, 퀵 정렬의 경우 가장 큰 부분 리스트로부터 시작해서 가장 작은 부분 리스트에서 종료되지만 합병 정렬의 경우 가장 작은 부분 리스트로부터 시작해서 가장 큰 부분 리스트에서 종료됩니다. 

 

퀵 정렬 - 스택 필요, 불안정적인 정렬 (같은 값일 때 순서가 변할 수 있음), 정복-> 분할

합병 정렬 - 스택 불필요, 안정적인 정렬 (같은 값이어도 정렬 후 순서가 변하지 않음), 분할 -> 정복

 

정렬 방법

1. 리스트의 크기가 1 이 될때까지 분할한다.

2. 부분 리스트를 합병한다. (이때 두 부분리스트 원소의 크기를 비교해가며 합병하기때문에 정렬된 형태로 합병되어 나가집니다. 코드 참고하세요!) 

 

소스코드(파이썬)

from collections import deque

def merge_sort(a):
    n = len(a)
    result = []
    
    if n <= 1:
        return a
    
    mid = n//2
    
    g1 = deque(merge_sort(a[:mid]))
    g2 = deque(merge_sort(a[mid:]))

    while g1 and g2:
        print(g1,g2)
        if g1[0] < g2[0]:
            result.append(g1.popleft()) // pop(0)은 시간복잡도가 O(n)이라 deque 의 popleft사용
        else:
            result.append(g2.popleft())
            
    while g1:
        result.append(g1.popleft())
    
    while g2:
        result.append(g2.popleft())
    
    return result

특징: 안정적인 정렬 (같은 값이어도 정렬 후 순서가 변하지 않음)

 

3. 힙 정렬 

---

힙(우선순위 큐)를 사용해 정렬하는 방법으로 오름차순 정렬시 최소 힙을 내림차순 정렬시에는 최대 힙을 구성하면 됩니다. 

* 오름차순 정렬 - 최소 힙,   내림차순 정렬 - 최대 힙 

여기서 힙이란? 

최대 힙 - 부모 노드 키 값이 자식 노드 키 값 보다 커야하는 조건을 만족하는 완전이진트리

최소 힙 - 부모 노드 키 값이 자식 노드 키 값 보다 작아야하는 조건을 만족하는 완전이진트리

* 완전이진트리 - 노드를 부모노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드 순으로 추가한 이진 트리  

참고) 1차원 배열과 힙

정렬 방법

1. n개의 노드에 대해 완전이진트리 구성

2. 최대 힙 구성 

3. 루트노드와 말단 노드 교환

4. 최대 힙 구성

5. 2~4 과정 반복

 

소스코드(파이썬)

def heapify(ls, index, heap_size):
    largest = index
    left_index = 2*index + 1
    right_index = 2*index + 2
    
    if left_index < heap_size and ls[left_index] > ls[largest]:
        largest = left_index
    
    if right_index < heap_size and ls[right_index] > ls[largest]:
        largest = right_index
    
    if largest != index:
        ls[largest], ls[index] = ls[index], ls[largest]
        
        heapify(ls, largest, heap_size)
    
    
def heap_sort(ls: list) -> list:
    for i in range(len(ls) // 2 - 1, -1, -1):
        heapify(ls, i, len(ls))
    
    for i in range(len(ls)-1, 0, -1):
        ls[0], ls[i] = ls[i], ls[0]
        heapify(ls,0,i)
        
    return ls

특징: 제자리 정렬 알고리즘 (정렬에 사용되는 추가적인 저장공간이 매우 작음), 불안정적인 정렬 (같은 값일 때 순서가 변할 수 있음)