정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것을 말함.
정렬이 필요한 이유
데이터를 정렬하면 원하는 데이터를 쉽게 찾을 수 있다. 그 예시로 이진 탐색 트리가 있다. 만약 오름 차순으로 정렬이 되어있는 데이터가 있다면, 큰 수를 찾을 때는 오른쪽부터 찾는 것이 훨씬 쉽고 빠르게 찾을 것이다. 정렬은 알고리즘의 효율을 크게 높여줍니다.
이번에 알아볼 정렬은 다음과 같다.
| 정렬 방법 | 최악의 경우 | 최선의 경우 | 특이점 |
| 삽입 정렬 | O(N ^ 2) | O(N) | 데이터가 거의 정렬되어 있을 때는 최고의 성능을 발휘함. |
| 병합 정렬 | O(N log N) | O(N log N) | 안정적인 성능으로 정렬할 수 있다. 병합 과정에서 추가적인 메모리가 요구된다. |
| 힙 정렬 | O(N log N) | O(N log N) | 안정적인 성능으로 정렬할 수 있다 데이터를 삽입과 동시에 빠르게 정렬할 수 있다. |
| 계수 정렬 | O(N + K) | O(N + K) | 데이터에 의존적이므로 항상 사용 가능한 것은 아니다. |
| 위상 정렬 | O(V + E) | O(V + E) | 작업의 순서가 존재할 때 사용 되는 정렬 |
삽입 정렬(Insertion Sort)
먼저 배워볼 정렬은 삽입 정렬. 팀소트(Tim Sort) 의 기원이 되는 삽입 정렬과 병합 정렬 중 하나이다.
삽입 정렬은 데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬한다.
def insert_sort(x):
for i in range(1, len(x)):
j = i - 1
key = x[i]
while x[j] > key and j >= 0:
x[j+1] = x[j]
j = j - 1
x[j+1] = key
return x- 최초에는 정렬된 영역은 왼쪽 1개, 정렬되지 않은 영역을 나머지로 한다.
- 키와 정렬된 영역의 맨 끝 값부터 거슬러 올라가며 다음 처리를 한다.
- 키보다 크면 해당 값을 오른쪽으로 한 칸 밀어냄.
- 키보다 작거나 더 이상 비교할 값이 없으면 밀어낸 자리에 키를 넣음.
- 모든 데이터가 정렬된 영역이 될 때까지 2단계를 반복.
삽입 정렬의 시간 복잡도는 최악의 경우 O(N^2). 최선의 경우는 O(N)으로 이미 정렬되어 있는 경우이다.
병합 정렬(Merge Sort)
앞서 팀소트에 활용된 삽입 정렬과 함께 병합 정렬을 알아보자.
흔히 분할 정복(Divide and Conquer) 방식 중 하나로, 대표적으로 이진 탐색과 병합 정렬을 들 수 있다.
병합 정렬은 정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬하는 방식이다.
병합 정렬의 핵심은 '병합할 때 부분 정렬하는 부분을 어떻게 구현해야 하는가?' 이다.
- 각 데이터의 첫 번째 원소를 가리키는 포인터를 만든다.
- 포인터가 가리키는 두 값 중 작은 값을 선택해 새 저장 공간에 저장한다.
- 값이 선택된 포인터는 다음 위치의 값을 가리킨다.
- 새 저장 공간에 하나의 데이터가 완전히 저장될 때까지 과정 1을 반복한다.
- 그러고 나서 저장할 값이 남은 데이터의 값을 순서대로 새로운 저장 공간에 저장한다.
- 그러면 새로운 저장 공간에 두 개의 데이터가 정렬된 상태로 저장된다.
- 새로운 저장소에 저장된 값의 개수와 초기에 주어진 데이터에 들어 있는 값의 개수가 같을 때 까지 과정 1, 2를 반복한다.
병합 정렬의 시간 복잡도는 결국 병합 횟수가 결정한다. 나누는 횟수는 log N, 이를 합치는 횟수는 N log N(N개를 병합하는 과정을 log N번 진행). 따라서 시간 복잡도는 O(N log N)이다.
힙 정렬(Heap Sort)
힙 정렬은 힙이라는 자료구조를 사용해 정렬한다. 따라서 힙 정렬은 힙 자료구조가 무엇인지 먼저 알아보자.
힙 정렬을 하기 위해서는 먼저 주어진 데이터로 힙을 구축해야 한다. 정렬되지 않은 데이터로 어떻게 힙을 구축하는지 알아보고, 이후 힙을 활용해서 정렬하는 방법을 알아보자.
힙은 특정 규칙이 있는 이진 트리이다. 그리고 규칙에 따라 최대 힙, 최소 힙으로 나눕니다. 최대 힙은 부모 노드가 자식 노드보다 크고, 최소 힙은 부모 노드가 자식 노드보다 작습니다.
힙 구축 방법 : 최대 힙
최대 힙과 최소 힙은 힙을 구성하는 규칙만 다르고 나머지는 동일하다. 보통 힙 구축을 설명할 때는 이진 트리 그림을 놓고 설명하는 경우가 많지만, 무작위 배열이 있다고 가정하고 최대 힙을 구축하는 방법을 이진 트리 그림과 함께 알아보자.
- 현재 노드와 자식 노드의 값을 비교
- 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다.
- 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산을 종료함.
- 맞바꾼 자식 노드의 위치를 현재 노드로 하여 과정 1을 반복함
힙 정렬 과정 : 최대 힙
최대 힙에서 힙 정렬은 루트 노드가 가장 큰 값이므로 루트 노드의 값을 빼서 저장하기만 하면 된다. 다만 루트 노드의 값을 뺀 이후 최대 힙을 유지하는 것이 중요한 데, 이 과정에 대해서 알아보자. 루트 노드가 빠진 다음에도 나머지 원소들이 최대 힙을 유지할 수 있다면 우리는 힙에서 원소가 큰 순서대로 값을 가져올 수 있게 되므로 내림차순 정렬을 쉽게 할 수 있게 된다. 힙 정렬하는 과정을 나타내면 아래와 같다.
- 정렬되지 않은 데이터로 최대 힙을 구축함.
- 현재 최대 힙의 루트 노드와 마지막 노드를 맞바꾼다. 맞바꾼 뒤 마지막 노드는 최대 힙에서 제외한다.
- 현재 최대 힙은 마지막 노드가 루트 노드가 되었다. 따라서 최대 힙을 다시 구축한다. 루트 노드를 최대 힙으로 구축하고 과정 2를 수행한다. 이 과정은 최대 힙의 크기가 1이 될 때까지 반복.
힙 정렬 시간 복잡도
힙 정렬의 시간 복잡도는 O(N log N) 으로, 이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성하는 과정이 트리의 깊이 만큼 이루어지므로 O(log N)의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체 시간은 힙 구성시간과 n개의 데이터 삭제 및 재구성 시간을 포함한다. 따라서 시간 복잡도는
= (log N + log (N - 1) + ... + log 2)
= (log N + log (N - 1) + ... + log 2) + (log N + log (N - 1) + ... + log 2)
= (N log N)
우선순위 큐
우선순위 큐는 우선순위가 높은 데이터부터 먼저 처리하는 큐이다. 쉽게 말해 큐는 큐인데 우선 순위에 따라 팝을 하는 큐이다. 예를 들어 데이터의 값이 작을수록 우선순위가 높을 때의 우선순위 큐는 3, 1 순서로 데이터를 푸시하면 팝은 1, 3 순서로 한다. 우선순위 큐의 내부 동작은 힙과 매우 유사하므로 우선순위 큐를 구현할 때는 힙을 활용하는 것이 효율적이다.
우선순위 큐가 동작하는 방식
본 글에서는 우선순위 큐의 우선순위 기준은 작은 값일수록 우선순위가 높다라고 가정하겠다.
- 빈 우선순위 큐를 하나 선언한다. 형태는 큐와 동일.
- 3을 삽입. 빈 큐이므로 별 다른 우선순위를 생각하지 않고 맨 앞에 푸시.
- 이어허 1을 삽입합니다. 1은 3보다 작으므로 우선순위가 높다. 따라서 1을 3 앞으로 삽입한다. 이렇게 하면 3보다 1이 먼저 팝 된다.
- 팝하는 과정. 앞서 언급했듯 3 앞에 1을 삽입했으므로 팝하면 1이 나온다.
우선순위 큐가 동작하는 방식은 매우 간단해서 쉽게 이해할 수 있을 것이다. 그리고 우선순위에 따라 데이터를 팝할 수 있으므로 정렬과 깊은 연관이 있다는 것도 알았을 것이다. 예를 들어 입력 받은 자연수를 오름차순으로 정렬받고 싶다면 방금 살펴본 '작은 값일수록 우선순위가 높은 우선순위 큐'에 마구 자연수를 집어넣고 팝하면 원하는 정렬 결과를 얻을 수 있을 것이다.
그러면 '우선순위 큐를 구현할 때 큐에 데이터를 푸시할 때마다 어떤 정렬 알고리즘을 사용하던 아무 정렬 알고리즘이나 쓰면 되는거 아닌가?' 하는 의문이 들 수 있다. 하지만 효율을 생각하면 우선순위 큐는 힙으로 구현하는 것이 가장 좋다.
힙으로 우선순위 큐를 구현해야 하는 이유
우선순위 큐의 핵심 동작은 우선순위가 높은 데이터를 먼저 팝하는 것이다. 이를 위해 앞서 언급했던 것처럼 데이터를 푸시할 때마다 아무 정렬 알고리즘이나 사용해서 데이터를 우선순위에 맞게 정렬해도 가능하다. 하지만 최소 힙이나 최대 힙은 특정 값을 루트 노드에 유지하는 특징이 있고, 이는 우선순위 큐의 핵심 동작과 맞아 떨어지므로 힙을 활용하면 우선순위 큐를 효율적으로 구현할 수 있다는 것을 알 수 있다.
import heapq
# 빈 힙 생성
heap = []
# 값을 우선순위 큐에 삽입 (heappush)
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)
heapq.heappush(heap, 1)
# 현재 우선순위 큐의 상태 출력
print(heap) # [1, 5, 20, 10]
# 우선순위 큐에서 가작 작은 요소 확인 및 제거 (heappop)
print(heapq.heappop(heap)) # 1
print(heap) # [5, 10, 20]
print(heapq.heappop(heap)) # 5
print(heap) # [10, 20]
데이터 자체에 우선순위를 직접 정하고 싶다면 튜플 형태로 (우선순위, 데이터)를 heappush() 메서드에 전달하면 된다. 이에 대한 실습은 값이 클수록 우선순위를 높게 하는 방법을 하면서 같이 하려고 한다. 전 과정인 최대 힙을 이러한 방법으로 구성할 수 있다.
힙은 기본적으로 작은 수의 우선순위가 높게 설정되어 있기 때문에, 높은 값에 -1을 곱해준다면 우선순위가 뒤바뀌게 되어 절대값이 큰 수가 우선순위가 높은 힙으로 바뀌게 된다.
# maxHeap을 사용하려면 값에 대한 부호를 바꿔야 한다.
# 값이 음수로 바뀌기 때문에 값을 추출할 때 다시 부호를 바꿔야 한다.
class maxHeap :
def __init__(self) :
self.heap = []
def push(self, value):
heapq.heappush(self.heap, -value)
def pop(self):
return -heapq.heappop(self.heap)
max_heap = maxHeap()
max_heap.push(10)
max_heap.push(5)
max_heap.push(20)
max_heap.push(1)
print(max_heap.heap)
print(max_heap.pop())
print(max_heap.pop())
print(max_heap.pop())
print(max_heap.pop())이 방법은 힙에는 음수로 수가 저장된다.
import heapq
class maxHeap :
def __init__(self) :
self.heap = []
def push(self, value):
heapq.heappush(self.heap, (-value, value))
def pop(self):
return heapq.heappop(self.heap)[1]
max_heap = maxHeap()
max_heap.push(10)
max_heap.push(5)
max_heap.push(20)
max_heap.push(1)
print(max_heap.heap)
print(max_heap.pop())
print(max_heap.pop())
print(max_heap.pop())
print(max_heap.pop())이 방법은 튜플(tuple)형태로 저장을 하게 된다. 책에 제시된 코드보다는 이 코드를 더 선호한다.
음수로 push를 한 다음 pop 단계에서 다시 음수를 취해주면 양수가 되는 원리를 이용해도 되고, 음수를 키(우선순위)로, 양수를 값으로 넣어도 괜찮다는 생각이 든다.
import heapq
# 우선순위와 작업을 포함하는 리스트 생성
tasks = [(3, "작업 A"), (1, "작업 C"), (2, "작업 B")]
# 리스트를 힙으로 변환
heapq.heapify(tasks)
# 추가 작업 삽입
heapq.heappush(tasks, (0, "작업 D"))
# 현재 힙의 상태
print(tasks) # [(0, '작업 D'), (1, '작업 C'), (2, '작업 B'), (3, '작업 A')]
# 우선순위가 가장 높은 작업부터 pop
print(heapq.heappop(tasks)) # (0, '작업 D')
print(tasks) # [(1, '작업 C'), (3, '작업 A'), (2, '작업 B')]
리스트로 작업을 한 후 heapq.heapify 를 활용하는 방법도 있다.
우선순위 큐가 활용되는 분야
우선순위 큐는 데이터의 중요성 혹은 우선순위에 따라 처리해야 하는 경우 많이 활용된다.
- 작업 스케줄링 : 운영체제에서 프로세스나 스레드의 실행 순서를 결정할 때 우선순위 큐를 활용해서 중요한 작업을 먼저 처리
- 응급실 대기열 : 환자의 진료 우선순위를 결정하고, 중증의 환자를 먼저 치료
- 네트워크 트래픽 제어 : 패킷 스케줄링 및 트래픽 관리에서 중요하거나 긴급한 패킷을 먼저 처리
- 교통 네트워크 최적화 : 교통 체계를 분석하고 최적화하기 위한 최단 경로 알고리즘을 구현하기 위해 활용
위상 정렬(Topological Sort)
위상 정렬은 일의 순서가 있는 작업을 순서에 맞춰 정렬하는 알고리즘.
위상 정렬과 진입차수
위상 정렬은 자신을 향한 화살표 개수를 진입차수로 정의하여 진행한다.
from collections import deque
def topological_sort(graph):
# 그래프는 {노드: [인접노드 리스트]} 형태의 딕셔너리로 표현됩니다.
# 모든 노드의 진입 차수를 계산합니다.
in_degree = {u: 0 for u in graph} # 모든 노드에 대해 진입 차수를 0으로 초기화
for u in graph:
for v in graph[u]:
in_degree[v] += 1
# 진입 차수가 0인 노드를 큐에 넣습니다.
queue = deque([u for u in in_degree if in_degree[u] == 0])
# 위상 정렬을 수행한 결과를 담을 리스트입니다.
order = []
while queue:
u = queue.popleft() # 큐에서 원소를 꺼냅니다.
order.append(u) # 결과 리스트에 추가합니다.
for v in graph[u]:
in_degree[v] -= 1 # 해당 노드와 연결된 노드의 진입 차수를 1 감소
if in_degree[v] == 0:
queue.append(v) # 새로 진입 차수가 0이 된 노드를 큐에 추가합니다.
# 모든 노드를 방문했는지 확인합니다.
if len(order) == len(in_degree):
return order
else:
# 순환 구조가 있어 위상 정렬이 완료되지 않은 경우
return "DAG가 아니므로 위상 정렬을 수행할 수 없습니다."
# 예제 그래프
graph = {
'A': ['D'],
'B': ['G'],
'C': ['E'],
'D': ['E'],
'E': ['F'],
'F': ['G'],
'G': []
}
print(topological_sort(graph)) # ['A', 'B', 'C', 'D', 'E', 'F', 'G']지금 위 코드의 예시로는 ['A', 'B', 'C', 'D', 'E', 'F', 'G'] 가 나타나게 된다.
위상 정렬은 모든 정점과 간선을 딱 한 번씩만 지나므로 시간 복잡도는 O(|V| + |E|)가 됩니다.
계수 정렬(Counting Sort)
계수 정렬은 데이터에 의존하는 정렬 방식이다. 지금까지 배운 정렬들은 사용자가 정한 기준에 따라 정렬했다. 반면 계수 정렬은 데이터의 빈도수로 정렬한다.
def counting_sort(input, k):
# k는 입력 리스트 input에 있는 가장 큰 수입니다.
count = [0] * (k + 1) # k+1 크기의 카운트 배열을 생성합니다.
output = [0] * len(input) # 입력과 같은 길이의 출력 배열을 생성합니다.
# 각 요소의 출현 횟수를 세어 count 배열에 저장합니다.
for i in input:
count[i] += 1
# count 배열을 누적합 배열로 변환합니다.
for i in range(1, k + 1):
count[i] += count[i - 1]
# 입력 리스트를 뒤에서부터 순회하면서 output 배열을 채웁니다.
for i in range(len(input) - 1, -1, -1):
count[input[i]] -= 1
output[count[input[i]]] = input[i]
return output
lst = [1, 5, 5, 2, 3, 7, 2, 4, 8, 1]
k = max(lst)
sorted_list = counting_sort(lst, k)
print(sorted_list) # [1, 1, 2, 2, 3, 4, 5, 5, 7, 8]코드에서 보듯 1이 2개이므로 count[1] = 2이다. 나머지도 마찬가지로 빈도수를 채운다. 이렇게 빈도수를 다 채운 다음에는 우선 순위가 높은 데이터부터 빈도수만큼 출력하는 것이 계수 정렬입니다. 이를테면 빈도수 배열에서 인덱스 오름차순으로 각 인덱스를 빈도수만큼 출력하면 자연스럽게 오름차순으로 정렬한 배열이 나온다.
계수 정렬의 한계
계수 정렬의 핵심 동작은 앞서 본 것처럼 빈도수를 세어 빈도수 배열에 저장하는 것이다. 그래서 빈도수 배열에 저장할 값의 범위가 듬성듬성 있거나, 음수가 있으면 계수 정렬을 하기 매우 곤란해진다. 이를테면 다음과 같이 -150, 500, 10억과 같은 값의 빈도수를 측정하여 빈도수 배열에 저장하는 건 비효율적이다. -150이라는 값은 음수이므로 배열의 인덱스로 표현할 수 없고, -150과 500 사이의 공간 낭비도 역시 비효율적이라고 할 수 있다. 크기가 10억 이상인 배열을 만드는 것은 환경에 따라 어려울 수도 있다. 물론 다음 그림에서 가장 작은 값인 -150을 찾아서 전부 150을 더하면 계수 정렬을 활용할 수도 있겠지만 그만큼 추가 연산이 필요하기 때문에 다른 정렬을 고민해보는 것이 좋다.
계수 정렬의 시간복잡도
값이 N개인 데이터에 대해서 계수 정렬을 한다고 가정해보자. 데이터를 세는 과정은 전체 데이터를 한 번씩 체크하면 되므로 N번 탐색한다고 생각할 수 있다. 값이 최솟값 ~ 최댓값 범위 크기가 K라면 빈도수 배열에서 K + 1 만큼 탐색해야 하므로 계수 정렬의 시간 복잡도는
O(N + K)라고 생각할 수 있다.