파이썬 정렬

해당 내용은 코딩 테스트 합격자 되기의 저자께서 작성한 코드를 기반으로 작성했습니다.
출처

계수 정렬 (Counting Sort)

계수 정렬이란, 정수 배열을 정렬함에 있어 비교를 진행하지 않고 정렬하는 방법으로 O(n+k)의 시간복잡도를 가진다. (n: 배열 크기, k: 최댓값과 최솟값 차이)

이는 입력 데이터의 분포가 정해져 있는 경우 매우 효율적이다.

계수 정렬의 동작 과정은 다음과 같다.

1. 입력 배열을 순회하며 각 숫자의 개수를 센다.
2. 개수를 기반으로 숫자를 정렬된 위치에 배치한다.
3. 정렬된 결과를 반환한다.

예를 들어, 입력 배열이 [4, 2, 2, 8, 3, 3, 1] 인 경우, 최댓값을 찾아 그만큼의 리스트를 만든 뒤, 각 숫자가 출현한 빈도를 센다.

-> [0, 1, 2, 2, 1, 0, 0, 0, 1]

코드로 나타내면 다음과 같다.

def counting_sort(arr):
	max_val = max(arr)
    count = [0] * (max_val + 1)
    
    for num in arr:							# 각 원소 개수 세기
    	count[num] += 1
    
    sorted_arr = []
    
    for i in range(len(count)):				# 정렬된 배열 생성
    	sorted_arr.extend([i] * count[i])
    
    return sorted_arr

arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

----------------------
[1, 2, 2, 3, 3, 4, 8]

---

삽입 정렬 (Insertion Sort)

삽입 정렬은 배열의 각 원소를 이미 정렬된 부분에 삽입하는 방식으로 동작하는 정렬 방식으로, 배열에 담긴 모든 원소에 대해 반복하며 정렬한다.

시간 복잡도의 경우 모든 배열을 돌아야 하기 때문에 아래와 같다.

• 최선의 경우: O(n)
• 최악의 경우: O(n^2)

예를 들어 입력 배열이 [5, 3, 8, 4, 2]인 경우, 진행되는 프로세스는 아래와 같다.

1. key = 3, [5, 5, 8, 4, 2] -> [3, 5, 8, 4, 2]
2. key = 8 8은 다른 숫자보다 크기에 앞으로 땡겨질 수 없어, 변동사항 없음
3. key = 4, [3, 5, 8, 8, 2] -> [3, 5, 5, 8, 2] -> [3, 4, 5, 8, 2]
4. key = 2, [3, 4, 5, 8, 8] -> [3, 4, 5, 5, 8] -> [3, 4, 4, 5, 8] -> [3, 3, 4, 5, 8] -> [2, 3, 4, 5, 8]

코드로 나타내면 아래와 같다.

def insertion_sort(arr):
	for i in range(1, len(arr)):
    	key = arr[i]
        j = i-1
        
        while j >= 0 and key < arr[j]:
        	arr[j+1] = arr[j]
            j -= 1
            
        arr[j+1] = key
    
    return arr
    
arr = [5, 3, 8, 4, 2]
sorted_arr = insertion_arr(arr)
print(sorted_arr)

---

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복(divide and conquer) 전략을 사용하는 정렬 알고리즘으로, 배열을 절반으로 계속해서 분할하다가 길이가 1이 되면, 이를 기준으로 다시 합치면서 정렬을 진행한다.

실질적인 정렬은 두 부분 배열을 합치는 과정에서 정렬이 이루어지기 때문에, 병합 정렬이라고 표현한다.

병합 정렬은 안정적인 정렬로, 순서가 같은 원소들의 상대적 순서가 정렬 후에도 유지되는 특징을 가진다.

시간복잡도는 O(n log n)으로, 배열을 절반씩 분할하는데 log n의 시간이 소요되며, 각 분할마다 n만큼의 연산이 필요하므로 n log n이 된다.

예를 들어 입력 배열이 [38, 27, 43, 3, 9, 82, 10]이라고 하면,

1. 입력 배열을 절반씩 분할한다.
- [38, 27, 43, 3] <--> [9, 82, 10]


2. 각각의 배열을 다시 절반씩 분할한다.
- [38, 27] <--> [43, 3]
- [9] <--> [82, 10]


3. 분할된 배열들을 정렬하며 병합한다.
- [38, 27] --> [27, 38]
- [43, 3] --> [3, 43]
- [82, 10] --> [10, 82]
- [9]


4. 이전 단계의 정렬된 배열들을 병합한다.
- [27, 38] and [3, 43] --> [3, 27, 38, 43]
- [9] and [10, 82] --> [9, 10, 82]


5. 최종적으로 병합하며 완전히 정렬된 배열을 얻는다.
- [3, 27, 38, 43] and [9, 10, 82] --> [3, 9, 10, 27, 38, 43, 82]

이를 코드로 나타내면 다음과 같다.

def merge_sort(arr):
	if len(arr) <= 1:		# 리스트의 길이가 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):
	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):				# 남은 원소들 추가
    	result.append(left[i])
        i += 1
        
    while j < len(right):				# 남은 원소들 추가
    	result.append(right[j])
        j += 1
        
    return result
    
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)

-------------------------
[3, 9, 10, 27, 38, 43, 82]    

---

위상 정렬 (Topological Sort)

위상 정렬은 방향성이 있는 그래프에서 노드를 선형 순서로 나열하는 방법이다. 이때 순서는 그래프의 간선 방향을 거스르지 않아야 한다.

즉, A -> B의 간선이 있는 경우, A는 B보다 선행되어야 한다. 또한, 그래프에 사이클이 존재하는 경우 위상 정렬을 수행할 수 없다.

위상 정렬의 시간복잡도는 그래프의 노드 수를 V, 간선 수를 E라고 할 때, O(V+E)가 된다.

위상 정렬 과정은 다음과 같다.

1. 진입 차수가 0인 노드를 선택
2. 선택한 노드와 연결된 간선을 제거
3. 진입 차수 갱신
4. 진입 차수가 0인 노드 선택
5. 1~4 반복

만약 진입 차수가 다음과 같은 그래프가 있다고 생각해보면, 노드(진입 차수)로 표현

0(0) --> 1(1) --> 3(1)
|        |        |
v        v        v
2(1) --> 4(2) --> 5(2)

결과 리스트: []
큐: []

---

• 진입 차수가 0인 노드(0)을 큐에 추가
  결과 리스트: []
큐: [0]

• 큐에서 노드를 꺼내 결과 리스트에 추가
  결과 리스트: [0]
큐: []

• 현재 노드 0 처리
  진입 차수: 0(0), 1(0), 2(0), 3(1), 4(2), 5(2)
큐: []

---

• 진입 차수가 0인 노드(1)을 큐에 추가
  결과 리스트: [0]
큐: [1]

• 큐에서 노드를 꺼내 결과 리스트에 추가
  결과 리스트: [0, 1]
큐: []

• 현재 노드 1 처리
  진입 차수: 0(0), 1(0), 2(0), 3(0), 4(1), 5(2)
큐: []

---

• 진입 차수가 0인 노드(2)을 큐에 추가
  결과 리스트: [0, 1]
큐: [2]

• 큐에서 노드를 꺼내 결과 리스트에 추가
  결과 리스트: [0, 1, 2]
큐: []

• 현재 노드 2 처리
  진입 차수: 0(0), 1(0), 2(0), 3(0), 4(0), 5(2)
큐: []

---

• 진입 차수가 0인 노드(3)을 큐에 추가
  결과 리스트: [0, 1, 2]
큐: [3]

• 큐에서 노드를 꺼내 결과 리스트에 추가
  결과 리스트: [0, 1, 2, 3]
큐: []

• 현재 노드 3 처리
  진입 차수: 0(0), 1(0), 2(0), 3(0), 4(0), 5(1)
큐: []

---

• 진입 차수가 0인 노드(4)을 큐에 추가
  결과 리스트: [0, 1, 2, 3]
큐: [4]

• 큐에서 노드를 꺼내 결과 리스트에 추가
  결과 리스트: [0, 1, 2, 3, 4]
큐: []

• 현재 노드 4 처리
  진입 차수: 0(0), 1(0), 2(0), 3(0), 4(0), 5(0)
큐: []

---

• 진입 차수가 0인 노드(5)을 큐에 추가
  결과 리스트: [0, 1, 2, 3]
큐: [4]

• 큐에서 노드를 꺼내 결과 리스트에 추가
  결과 리스트: [0, 1, 2, 3, 4, 5]
큐: []

• 종료
  결과 리스트: [0, 1, 2, 3, 4, 5]

---

이를 작성한 코드는 다음과 같다.

from collections import deque

def topology_sort(graph):
	# 진입 차수 계산
    num_nodes = len(graph)
    in_degree = [0] * num_nodes
    
    for nodes in graph:
    	for neighbor in graph[node]:	# 진입 수 계산
        	in_degree[neighbor] += 1
    
    result = [] 		# 결과 리스트
    
    # 진입 차수가 0인 노드를 큐에 추가
    queue = deque()
    
    for node in range(num_nodes):
    	if in_degree[node] == 0:
        	queue.append(node)
            
    # 위상 정렬 
    while queue:
    	# 큐에서 노드를 꺼내 결과 리스트에 추가
        current_node = queue.popleft()
        result.append(current_node)
        
        # 해당 노드에서 나가는 간선 제거 및 진입 차수 갱신
        for neighbor in graph[current_node]:
        	in_degree[neighbor] -= 1
            
            if in_degree[neighbor] == 0:
            	queue.append(neighbor)
	
    if len(result) != num_nodes:
    	return "그래프에 사이클이 존재합니다!"
    
    return result
    
graph = {
	0: [1, 2],
    1: [3, 4],
    2: [4],
    3: [5],
    4: [5],
    5: []
}

result = topological_sort(graph)

if isinstance(result, list):			# result가 list 타입인지 확인
	print("위상 정렬 결과: ", result)	
else:
	print(result)

--------------------------------
위상 정렬 결과: [0, 1, 2, 3, 4, 5]