[코테스터디] 정렬

팀 정렬(Tim Sort)

파이썬에서 주로 사용되는 고성능 정렬 알고리즘이다.

주로 `sorted`와 `sort` 이 두가지로 사용되며 이 둘은 차이점이 존재한다.

• `sort`는 리스트 자체를 정렬하는 제자리 정렬(in-place Sort)이므로 결과를 리턴할 필요 없이 정렬 후 적용 시켜버린다.

 

`sort`와 `sorted`의 인자인 `key`에 함수를 넣을 수 있다. 

일반적으로 람다 함수를 넣는 경우가 있는데 직접 함수를 만들어서 넣어도 된다.

만약 특정 조건으로 정렬을 하고 싶을 때 다음과 같이 사용하면 된다.

공식문서 참조↗

---

계수 정렬(Counting Sort)

시간 복잡도	공간 복잡도
O(N)	O(N)

 

배열의 인덱스를 특정 값으로 사용하는 정렬 알고리즘이다. 

예를 들어 다음과 같이 첫번째 줄은 1부터 10,000,000개의 사이의 수가 주어지는데 두번째 줄부터 이 숫자의 범위는 10,000보다 작거나 같다고 한다. 그럼 N개의 줄에 오름차순으로 정렬한 결과를 하나씩 출력하는 문제다. 해당 문제는 백준에서 가져온 문제↗이다. 

10
5
2
3
1
4
2
3
5
1
7

 

여기서, 파이썬의 기본 정렬(Timsort, `sort()`)을 사용하면 N logN의 시간 복잡도를 갖기 때문에 1천만 개의 연산을 하기엔 부족하다. 

그러나 문제에선 10,000 보다 작다고 나와 있으므로 0부터 10,001 까지의 범위를 지정하고 해당 인덱스의 횟수를 카운팅하면 해결할 수 있다.

예제에서는 1부터 7까지의 숫자가 있어 다음과 같이 간추려 도식화했다.

---

병합 정렬(Counting Sort)

시간 복잡도	공간 복잡도
O(N logN)	O(N log N)

 

Divide and Conquer라는 말 그대로 배열의 데이터들을 분할 한 후에 다시 결합하는 과정을 말한다.

결합하는 과정에서 정렬이 일어나는데 우선, 순서는 다음과 같다.

 

1. 만약 해당 리스트의 길이가 0 혹은 1인 경우에는 이미 정렬된 상태이므로 종료한다.
2. 그렇지 않은 경우 리스트를 1/2으로 잘라 두개의 리스트로 나눈다.
3. 왼쪽과 오른쪽 리스트를 재귀적으로 합병 정렬(나누었다가 다시 합친다.)한다.
   1. 이때 리스트의 원소가 0 혹은 1인 경우는 정렬할 수 없으므로 반환된 값끼리 합병을 시작한다.
   2. 합병을 시작할 때 값끼리 비교가 이루어지며 비교 결과를 기반으로 정렬된다. 
4. 정렬된 두 리스트를 다시 하나로 합친다.

병합 정렬은 안정 정렬에 속하는 정렬 알고리즘이다.

입력 데이터가 무엇이든 항상 정렬 시간은 동일하다. 그러나 배열의 길이가 큰 경우 이동시간이 많아지므로 이런 경우에 배열대신 연결리스트로 구성하면 좀 더 효율적인 알고리즘이 된다. 

병합 정렬 예제

이번엔 파이썬을 통해 병합 정렬을 구현해보자.

우선, 첫번째로 해당 리스트의 길이가 1 이하인 경우 이미 정렬된 상태이므로 종료한다.

def merge_sort(array):

    # 1. 만약 해당 리스트의 길이가 0 혹은 1인 경우에는 이미 정렬된 상태이므로 종료한다.
    if len(array) <= 1:
        return array

 

그 다음 해당 리스트를 두개로 잘라 리스트를 나누는 분할(Divide) 작업이 들어간다. 

이때 분할 작업은 일일히 다 작성하는 것보다 재귀용법을 사용해 재귀적으로 작업하는 것이 좋다. 

만약 해당 배열의 길이가 1이하가 되면 해당 원소를 반환하게 된다.

    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

 

그럼 병합 정렬 로직을 작성해보자.

이전 까지 `//2` 연산을 통해 좌 우측으로 하나가 될때까지 배열을 나누었다. 이번엔 합치는 작업이다.

    i, j, k = 0,0,0 # 좌, 우, 임시 배열의 포인터
    while i < len(left) and j < len(right):
        if left[i] < right[j]: # 우측 배열의 원소보다 좌측 배열의 원소가 큰경우 임시배열에 넣고 인덱스 증가
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[i]
            j += 1
        k += 1 # 값을 채우면 임시 배열의 인덱스 증가

합병이 될 두 배열이 이미 정렬되어있기 때문에 순차적으로 비교하면서 정렬할 수 있다.

합병 정렬은 순차적으로 비교하면서 정렬하므로 LinkedList(연결리스트)의 정렬을 할때 효율적이다.
이유는 연결리스트는 다음 값을 가리키는 포인터와 데이터로 이루어져 있는데 가리키는 포인터만 순차적으로 변경하면 되기 때문에 데이터를 이동시킬 필요가 없어진다. 

 

마지막으로, 남은값 채우기다.

만약 한쪽 배열의 데이터를 다 채운 경우, 나머지 한쪽의 데이터가 남았을 때 채우면 된다. 

    if i == len(left): # 왼쪽 배열을 다채운 경우 오른쪽 데이터를 다채울 때까지 데이터 넣기
        while j < len(right): 
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right): # 오른쪽 배열을 다채운 경우 왼쪽 데이터를 다채울 때까지 데이터 넣기
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array # 정렬된 배열 반환

---

위상 정렬(Topology Sort)

시간 복잡도	공간 복잡도
O(V+E)	O(V+E)

 

순서가 정해진 작업을 잘 지키면서 수행하는 알고리즘으로 순서 결정(방향성)이 중요한 알고리즘이다.

 

1. 진입차수가 없는 노드(시작노드)를 큐에 삽입한다.
2. 큐에서 원소를 꺼내 원소의 간선을 제거한다.
3. 다시, 진입차수가 없는 노드를 큐에 삽입한다. 

만약, 모든 원소를 방문하기 전 큐가 빈다면(진입차수가 없는 노드가 없다) 사이클이 존재하는 것이다. 기본적으로 위상정렬은 사이클이 존재하면 안된다. 

위상 정렬 예제

해당 문제는 이것이 취업을 위한 코딩 테스트다. with 파이썬 에서 가져온 문제이다. 

다음 그림처럼 강의 커리큘럼이 있다고 가정했을 때, N개의 강의를 듣기 위한 최소 시간을 구한다고 가정해보자.

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

 

우선, 해당 노드들의 개수와 노드들의 대한 진입 차수를 입력 받는다. 

v = int(input()) # 노드 개수 5
indegree = [0] * (v+1) # 진입차수 초기화
graph = [[] for i in range(v+1)] # 그래프
time = [0] * v+1 # 각 강의 별 시간

for i in range(1, v+1):
	data = list(map(int, input().split()) # 시간 진입 차수
    time[i] = data[0] # 시간
    
    for x in data[1:-1]:
        indegree[i] += 1 # 진입차수 개수 
        graph[x].append(i) # 진입차수 추가

 

위상 정렬 함수를 작성해 실제로 결과를 출력할 예정이다.

먼저 진입 차수가 없는 노드를 큐에 삽입해야 한다. 해당 그림에서 진입차수가 없는 노드는 첫번째 노드(10시간)이다. 

import heapq
import copy

def topology_sort():
	result = copy.deepcopy(time)
    heap = []
    
    for i in range(1, v+1):
    	if indegree[i] == 0:
        	heapq.heappush(heap, i) # 진입차수가 0인 경우 힙에 넣는다.

 

그다음 큐가 빌때 까지 큐에서 원소를 꺼내 원소와 연결된 간선을 제거한다. 진입차수의 개수도 제거한다.

	while heap:
		now = heapq.heappop(heap)
		for i in graph[now]: # 연결된 노드를 확인
			result[i] = max(result[i], result[now] + time[i]) 
			indegree[i] -= 1 # 진입 차수 제거
            
			# 새로운 진입 차수가 0이 되는 노드를 큐에 다시 삽입 한다.
			if indgree[i] == 0:
				heapq.heappush(heap, i)

 

그다음 반복적으로 진입차수가 없는 노드를 큐에 삽입해 각 최종 시간을 구하면 된다.

	for i in range(1, v+1):
    	print(result[i]