정렬 알고리즘 2 - Merge/Quick/Heap/Radix/Counting Sort

이번 시간에는 O(N^2) 정렬 알고리즘보다 조금은 복잡하지만, 더 효율적인 정렬 방법에 대해 학습해보도록 하겠습니다.

1. Merge Sort

1) 개념

병합 정렬은 Divide & Conquer 기법과 재귀 호출(반복문)을 사용하는 정렬 알고리즘이다.

※ Divide & Conquer
분할 정복은 큰 문제를 작은 문제로 분할하여 해결한 후, 해결 결과를 차례로 병합해나가며 전체 문제의 해답을 알아내는 설계 전략이다. 분할 정복법은 Merge Sort, Quick Sort, Binary Search 등 다양한 알고리즘에서 활용되는 매우 중요한 기법이다. 분할 정복은 아래의 세 단계로 구성된다.

• 분할(Divide): 큰 문제를 더 이상 나눌 수 없을 때까지 분할하여 해결하기 쉬운 문제로 만드는 단계
• 정복(Conquer): 분할된 문제가 충분히 작다고 판단되어, 해당 문제에 대한 해답을 도출하는 단계
• 결합(Combine): 분할된 문제의 해결 결과를 결합하여 결과적으로 원래 문제에 대한 해답을 얻는 단계

병합 정렬에는 아래의 두 가지 메서드가 사용된다.

① merge_sort

• 주어진 배열을 요소가 하나만 남을 때까지, 재귀적으로 절반씩 분할한다.
• 요소가 하나만 남았을 때, merge 메서드를 호출한다.

② merge

• 정렬된 결과를 저장할 result 배열을 새로 생성한다.
• left 배열과 right 배열의 인덱스를 추적할 i, j의 초기 값을 0으로 설정한다.
• i와 j 중 어느 하나라도 배열의 끝 인덱스에 도달하면 루프를 멈추고, left 또는 right 배열에 남아있는 값들을 result에 차례로 append 한다.
• 예를 들어 i가 끝 인덱스에 도달했다면, right 배열의 j번 인덱스부터 끝 인덱스까지를 result 배열에 append 해야 할 것이다.

2) 구현

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = arr[:mid] # 0번 ~ mid-1번 인덱스까지
    right = arr[mid:] # mid번 ~ 끝 인덱스까지
	
    # 재귀호출을 통해 하나의 요소만 남을 때까지 분할
    left = merge_sort(left)
    right = merge_sort(right)

    # 해답을 얻을 때까지 작은 배열을 계속해서 병합
    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
            
    while i < len(left): # j가 끝에 도달
        result.append(left[i])
        i += 1
        
    while j < len(right): # i가 끝에 도달
        result.append(right[j])
        j += 1
        
    return result
    
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print(sorted_arr) # [5, 6, 7, 11, 12, 13] 출력

2. Quick Sort

1) 개념

퀵 정렬도 Divide & Conquer 기법을 사용하는 정렬 알고리즘이다. 하지만, 배열을 정확히 절반으로 분할하는 Merge Sort와는 달리, Quick Sort에서는 배열을 비균등하게 분할한다. 즉, mid 변수를 기점으로 배열을 분할하지 않고, pivot이라는 임의 선택된 변수를 기점으로 배열을 분할한다는 것이다. 퀵 정렬은 루프가 실행될 때마다 pivot 값이 정렬되어야 할 위치를 찾아가는 특징이 있다.

Quick Sort에 사용할 pivot을 선정하기 위해 아래와 같은 방법을 고려해볼 수 있다.

• 배열의 첫번째나 가운데 또는, 마지막 원소를 pivot으로 선정
• 첫번째, 가운데, 마지막 원소 중 중간값(Median of Three)을 pivot으로 선정
• 무작위로 선택된 원소를 pivot으로 선정

2) 구현

여기서는 가장 기본적인 방법인 첫번째 방법(가운데 원소를 pivot으로 선택)을 사용하여 퀵 정렬을 구현해볼 것이다. 원래 Quick Sort는 다소 복잡한 방식으로 구현되지만, 파이썬에서는 List Comprehension을 이용해 매우 직관적이고 간단하게 구현할 수 있다.

def quick_sort(arr):
	if len(arr) <= 1: # 탈출 조건
		return arr
	
	pivot = arr[len(arr) // 2] # arr[0] 또는 arr[len(arr) - 1]도 가능
	
    # 리스트 컴프리헨션을 이용해 배열 생성
	left = [x for x in arr if x < pivot] # arr의 각 원소 x 중 pivot보다 작은 x만 left 배열에 포함  
	mid = [x for x in arr if x == pivot] # arr의 각 원소 x 중 pivot과 동일한 x만 mid 배열에 포함(중복 값 고려)  
	right = [x for x in arr if x > pivot] # arr의 각 원소 x 중 pivot보다 큰 x만 right 배열에 포함  
	
	return quick_sort(left) + mid + quick_sort(right) # 리스트 병합에 '+' 연산자를 사용 가능

arr = [20, 30, 12, 15, 22, 8]
sorted_arr = quick_sort(arr)
print(sorted_arr)

마찬가지로, left 배열과 right 배열의 부등호 방향만 바꾸어 내림차순으로 정렬할 수 있다.

3. Heap Sort

1) 개념

힙 정렬을 이용해 주어진 배열을 오름차순으로 정렬하기 위해서는 Max Heap을 구성해야 하고, 내림차순으로 정렬하기 위해서는 Min Heap을 구성해야 한다. 여기서 Max Heap은 부모 노드가 자식 노드보다 항상 크거나 같은 값을 가지는 힙이며, Min Heap은 부모 노드가 자식 노드보다 항상 작거나 같은 값을 가지는 힙이다.

※ Heap
Heap 자료 구조는 Complete Binary Tree(마지막 레벨을 제외한 모든 레벨은 노드로 꽉 차 있고, 마지막 레벨의 노드들은 왼쪽부터 차례로 채워지는 이진 트리)의 노드 중에서 키 값이 가장 크거나 가장 작은 노드를 찾기 위한 목적으로 사용된다. 즉, 최대/최소 값을 구하는데 용이한 자료구조이다.

Heap 자료 구조의 특성을 이용하여 root 노드에 최대 값 또는 최소 값을 위치시킨 후, 이 값을 기존 배열에 맨 뒤로 보내는 방식으로 정렬을 수행할 수 있다. 일단은 Max Heap을 기준으로 Heap 정렬의 동작 방식에 대해 알아보기로 하자. 힙 정렬에는 아래의 두가지 메서드가 사용된다.

① heapify()

• 입력받은 배열을 Max Heap으로 구성하기 위해 사용하는 메서드로 Max Heap이 위배될 수 있는 상황(초기 배열 상태일 때 또는 노드의 위치가 변경될 때)마다 호출해야 한다.
• 정렬할 배열과, 기준 노드(부모 노드)의 idx, 배열의 size를 입력 인자로 받는다.
• 부모 노드의 인덱스가 idx일 때, l_chlid_idx는 (2 * i + 1)이 되고, r_child_idx는 (2 * i + 2)가 된다.
• largest_idx 변수에 초기 값으로 idx를 할당한 후, idx의 값을 l_child_idx의 값과 비교한다. 이 때, l_child_idx의 값이 더 크다면, largest_idx를 l_child_idx로 업데이트한다. 이후 r_child_idx의 값과 비교하여 동일한 로직을 수행한다.
• 좌우 자식들과의 비교가 끝났을 때 largets_idx의 값이 idx와 다르다면(기준 노드보다 자식 노드의 값이 더 커서 Max Heap을 위배한다면), arr[largest_idx]와 arr[idx]를 swap한다.
• 부모 노드와 자식 노드가 swap 되었으므로, 새롭게 자식이 된 node가 Max Heap을 만족할 수 있도록 다시 heapify()를 호출한다.

② heap_sort()

• 정렬할 배열을 입력 인자로 받는다.
• 배열의 size가 N일 때, 부모 노드의 인덱스 중 가장 높은 값은 N // 2 - 1이 된다. 이 인덱스부터 1씩 줄여가면서 0에 도달할 때까지 heapify를 수행하면, Max Heap이 구성된다.
• Max Heap의 root 값(arr[0])을 arr의 맨 뒤의 값(arr[N-1])과 swap한 후, heapify() 메서드에 기존 arr를 전달하되, size는 N-1을 전달한다. 또한, root 노드의 값이 변경되었으므로, Max Heap을 구성하기 위해 0번 인덱스를 기준 노드로 전달해야 한다.

2) 구현

① Max Heap

• Max Heap을 이용하여 오름차순 정렬을 구현한다.

def heapify(arr, idx, size):
    l_child_idx = 2 * idx + 1
    r_child_idx = 2 * idx + 2
    largest_idx = idx # 초기화
    
    if l_child_idx < size and arr[largest_idx] < arr[l_child_idx]:
        largest_idx = l_child_idx
        
    if r_child_idx < size and arr[largest_idx] < arr[r_child_idx]:
        largest_idx = r_child_idx
        
    if largest_idx != idx: # 기준 노드보다 자식 노드의 값이 더 커서 Max Heap을 위배
        arr[largest_idx], arr[idx] = arr[idx], arr[largest_idx]
        heapify(arr, largest_idx, size) # 새롭게 자식이 된 node가 Max Heap을 만족할 수 있도록 다시 heapify()를 호출

def heap_sort(arr):
    N = len(arr)
    for i in range(N // 2 - 1, -1, -1):
        heapify(arr, i, N)

    for i in range(N-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i) 
    
    return arr

arr = [22, 35, 12, 11, 45, 25]
sorted_arr = heap_sort(arr)
print(sorted_arr)

② Min Heap

• Min Heap을 이용하여 내림차순 정렬을 구현한다.

def heapify(arr, idx, size):
    l_child_idx = 2 * idx + 1
    r_child_idx = 2 * idx + 2
    smallest_idx = idx # 초기화
    
    if l_child_idx < size and arr[smallest_idx] > arr[l_child_idx]:
        smallest_idx = l_child_idx
        
    if r_child_idx < size and arr[smallest_idx] > arr[r_child_idx]:
        smallest_idx = r_child_idx
        
    if smallest_idx != idx: # 기준 노드보다 자식 노드의 값이 더 작아서 Min Heap을 위배
        arr[smallest_idx], arr[idx] = arr[idx], arr[smallest_idx]
        heapify(arr, smallest_idx, size) # 새롭게 자식이 된 node가 Min Heap을 만족할 수 있도록 다시 heapify()를 호출

def heap_sort(arr):
    N = len(arr)
    for i in range(N // 2 - 1, -1, -1):
        heapify(arr, i, N)

    for i in range(N-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i) 
    
    return arr

arr = [22, 35, 12, 11, 45, 25]
sorted_arr = heap_sort(arr)
print(sorted_arr)

4. Radix Sort

1) 개념

기수 정렬은 낮은 자리수부터 비교하여 정렬해나가는 방식을 사용하는 알고리즘이다. 기수 정렬의 가장 큰 특징은 비교 연산을 수행할 필요가 없어 O(N) 시간 만에 정렬을 수행할 수 있다는 것이다. 하지만, 정렬에 추가적인 메모리를 필요로 한다는 점은 단점이다.

간단한 예시를 통해 기수 정렬의 정렬 로직에 대해 알아보자. 아래는 [153, 262, 037, 598, 433, 855, 067, 225, 874, 521]이라는 배열을 정렬하는 과정을 나타낸 것이다.

주어진 배열에서 원소를 popleft()한 후 1의 자리수에 맞는 인덱스에 배치한다. 배치가 완료되면, 이후에는 10의 자리수와 100의 자리수에 대해 동일한 로직을 수행한다. 이 과정이 완료되면, 자연히 정렬된 배열을 얻을 수 있게 된다. 이와 같은 기능을 구현하기 위해 필요한 핵심 개념은 아래와 같다.

① buckets

• size가 10인 배열이며, 각 원소는 deque이다.
• 주어진 배열을 deque 구조로 변환한 후, 하나씩 popLeft()하여 buckets 배열에 넣는다.
• buckets의 각 인덱스는 0~9까지의 숫자를 의미하며, 자리수가 n인 숫자를 n번 deque에 append() 한다.
• 각 자리수 배치가 끝날 때마다 buckets를 순회하면서 다시 하나의 완성된 deque로 변환한다.

② max_val

• 기수 정렬을 수행하기 위해서는 가장 큰 숫자의 자리수를 알아야 한다. 예를 들어 가장 큰 숫자가 874라면, 100의 자리수까지만 진행하면 된다.
• max() 함수를 이용해 주어진 배열에서의 최대 값을 알아낼 수 있으며, 1부터 10씩 곱해지는 digit 변수가 max_val보다 커질 때 반복문을 탈출한다.
• 참고로, num의 자리수(일의 자리, 십의 자리, ...)를 얻는 공식은 num // digit % 10이다.

2) 구현

from collections import deque

def radix_sort(arr):

    buckets = [deque() for _ in range(10)] # 각 원소가 deque인 buckets 배열 생성
    max_val = max(arr)
    deq = deque(arr) # 주어진 배열을 deque 구조로 변환
    digit = 1

    while max_val > digit: # 1부터 10씩 곱해지는 digit 변수가 max_val보다 커질 때 반복문을 탈출
        while deq: # deq의 모든 원소를 buckets에 append()
            num = deq.popleft()
            buckets[num // digit % 10].append(num)
    
    	# buckets를 순회하면서 다시 하나의 완성된 deque로 변환
        for bucket in buckets: # in reversed(buckets)로 변경하여 내림차순 정렬 가능
            while bucket:
                deq.append(bucket.popleft())
    
        digit *= 10

    return deq

arr = [153, 262, 37, 598, 433, 855, 67, 225, 874, 521]
sorted_arr = radix_sort(arr)
print(sorted_arr)

5. Counting Sort

1) 개념

구현이 다소 복잡한 기수 정렬보다 조금 더 실용적인 정렬 방법으로 계수 정렬이 있다. 계수 정렬과 기수 정렬의 공통점은 아래와 같다.

• 원소간 비교가 아닌 원소의 자리수나 값만을 이용하여 정렬을 수행
• O(N) 시간 안에 정렬을 수행
• 추가적인 메모리 공간이 필요

계수 정렬이 수행되는 과정을 알아보기 위해, [10, 8, 5, 7, 10, 3, 2]라는 데이터를 정렬해보자.

① 숫자의 범위만큼의 크기를 갖는 배열을 만든다.

• 모든 원소는 0으로 초기화된다.

② 각 숫자에 해당하는 인덱스의 원소를 1씩 증가시킨다.

③ 최종적으로 이 배열을 순회하면서, 원소가 0이 아닌 경우에 대해 해당 인덱스를 원소 값만큼 반복 출력한다.

위 과정이 완료되면, 자연히 정렬된 배열을 얻을 수 있다. 이처럼 계수 정렬은 범위가 작은 정수를 정렬하기에 매우 유리한 알고리즘이다.

2) 문제 풀이

>> 백준 10989번

이 문제를 보자마자, 아마 아래와 같은 풀이를 생각했을 것이다.

import sys
input = sys.stdin.readline

N = int(input())
lst = []

for i in range(N):
    lst.append(int(input()))

lst.sort() # 오름차순 정렬

for i in lst:
    print(i) # 원소 출력

그러나, 위 코드를 제출하면 메모리 초과가 발생한다. 이는 N의 크기가 최대 1천만이기 때문이다. 그렇다면, 이 문제를 어떻게 풀이할 수 있을까? 여기서 주목할 것은 숫자의 범위는 10000 이하로 N 값에 비해 비교적 작은 값이라는 것이다.

이 때 계수 정렬을 이용하면, size가 10000인 배열을 이용해 정렬을 수행할 수 있게 된다. 즉, 더 적은 메모리를 사용하면서도 더 빠르게 정렬을 수행할 수 있게 되는 것이다.

import sys
input = sys.stdin.readline

N = int(input())
lst = [0] * 10001 # 1 ~ 10000까지의 숫자를 인덱스로 표현하기 위해서는 배열의 사이즈가 10001이 되어야 함.

for i in range(N):
    lst[int(input())] += 1 # 각 숫자에 해당하는 인덱스의 원소를 1씩 증가시킴.

for i in range(10001): # 배열을 순회하면서
    if lst[i] != 0: # 원소가 0이 아닌 경우에 대해
        for j in range(lst[i]): # 해당 인덱스를 원소 값만큼 반복 출력
            print(i)

6. 정렬 알고리즘 비교

1) 사전 지식

① In-Place Sort

• 배열 내에서 정렬이 수행되기 때문에 추가적인 공간이 필요하지 않은 정렬 방식이다.
• O(1)의 공간 복잡도를 갖는다.
• 연속된 메모리를 할당받은 이후엔 더 이상의 메모리 할당이 필요 없기 때문에 공간지역성이 높다. 반면, 제자리 정렬이 아닌 정렬의 경우, 연속되지 않은 메모리를 사용하기 때문에 공간지역성이 낮다.

※ Cache Locality
캐시 메모리가 효율적으로 동작하기 위해서는 캐시에 저장될 데이터가 Locality(지역성)를 가지고 있어야 한다. 이를 Cache Locality라 하며, 크게 시간 지역성과 공간 지역성으로 구분된다.
시간 지역성이 높다는 말은 데이터의 읽기/쓰기를 위해 특정 메모리가 사용됐을 때, 가까운 시일 내에 해당 메모리가 다시 사용될 가능성이 높음을 의미한다. 또한, 공간 지역성이 높다는 말은 특정 데이터와 인접한 주소에 순서대로 접근한다는 의미로, 한 메모리 주소에 접근할 때 주변 블록을 전부 캐시에 가져옴으로써 작업 효율을 높인다.

② Stable Sort

• 동일한 값 사이의 순서가 정렬 후에도 보장되는 정렬 방식이다.
• 즉, 기존 배열의 정렬 순서를 유지한 채, 새로운 정렬 기준을 적용할 수 있다는 것이다.
• 예를 들어 학생의 이름을 가나다 순으로 정렬한 후 성적 순으로 다시 정렬할 때, 안정 정렬을 사용하여 같은 성적의 학생에 대해 가나다 순 정렬을 유지할 수 있다. (불안정 정렬 사용 시, 기존 가나다 순 정렬이 보장되지 않는다.)

2) 비교표