Algorithm - 정렬 알고리즘

O(n^2)

• 거품 정렬
• 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않으면 자리를 교환하며 정렬하는 알고리즘
• O(n^2)

• 선택 정렬
• 거품 정렬과 유사한 알고리즘으로, 원소를 넣을 위치는 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
• O(n^2)

• 삽입 정렬
• 손 안의 카드를 정렬하는 방법과 유사
• n번째 데이터는, n-1, n-2… 와 비교하면서 순서를 맞춘다.
• O(n^2)

O(nlogn)

• 병합 정렬
• 원소 개수가 0 또는 1이 될 때까지 쪼개고 쪼개서, 자른 순서의 역순으로 크기를 비교해 병합해 나가는 방법

• 힙 정렬
• 원소들을 전부 힙에 삽입한 후, 힙이 빌 때까지 pop을 반복

• 퀵 정렬
• 평균적인 상황에서 최고의 성능을 나타내는 알고리즘
• 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
• 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다
• 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

위상정렬

• 위상 정렬이란, 순서가 정해져 있지 않은 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다

• 선수과목의 구조에서 위상 정렬이 필요하다.
• 과목 A를 듣기 위해 과목 B, C를 먼저 들어야 하는 경우

• 위상 정렬을 하기 위한 그래프는 다음 조건이 필요하다.
• 간선이 방향성을 가진 그래프여야 한다
• 그래프 내부에 순환(사이클)이 없어야 한다.

• 위상 정렬의 시간복잡도는 O(V+E)이다.

• 과정
1. 진입 차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 해당 원소에 연결된 간선을 제거함
3. 간선을 제거한 후 진입 차수가 0이 된 정점을 큐에 삽입
4. 위 과정을 반복
→ 모든 정점을 방문하기 전에 큐가 비게 된다면 사이클이 존재하는 것이다.
→ 큐에서 원소를 꺼낸 순서가 위상 정렬의 결과가 된다.

• 구현

from collections import deque
 
v, e = map(int, input().split())
 
indegree = [0] * (v + 1) # 진입차수
graph = [[] for _ in range(v + 1)]
 
for _ in range(e): 
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
 
 
def topology_sort():
    result = []
    q = deque()
 
    for i in range(1, v + 1): # 우선 진입 차수가 0인 노드를 찾는다.
        if indegree[i] == 0:
            q.append(i)
 
    while q:
        now = q.popleft() 
        result.append(now) 
        for i in graph[now]:
            indegree[i] -= 1 # 연결된 노드들에 대해 간선 제거 -> 진입차수 -1
            if indegree[i] == 0: # 진입 차수가 0인 노드들을 deque에 append
                q.append(i)