1. 진입차수가 0인 노드를 큐에 넣기
2. 큐에서 꺼낸 노드에서 나가는 간선을 제거 (진입차수에 대한 값을 줄임)
3. 새롭게 진입차수가 0인 노드를 큐에 삽입
4. 큐가 빌때까지 2 ~ 3번을 반복

• O(V) ⇒ 차례대로 노드를 확인
• O(E) ⇒ 방문 중인 노드에서 출발하는 간선의 개수의 총합

• 비교를 하지 않는 일반 정렬
• 작업의 순서가 정해져 있을 때 일직선의 순서를 찾는 알고리즘
  • ex ) 대학생 되기 → 학과사이트 졸업하기 → 4학년기 → 정처기 합격하기 → 자격증 제출하기 → 졸업시험 합격하기 → 졸업하기
  • 주어진 엣지의 방향만 지키면 된다. 기초수학 → 물리 이고 기초수학 → 화학 일때 기초수학→물리 → 화학 도 괜찮고 기초 수학 →화학 →물리도 괜찮다
• 진입차수 : 특정 노드로 들어오는 간선의 개수
• 위상 정렬은 DAG 그래프에서만 적용 가능
  • DAG (비순환 방향그래프 : Directed Acyclic Graph) : 사이클이 없는 방향 그래프
• 시작점은 정점에 들어오는 간선이 없는 정점
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상정렬의 결과
• DFS를 이용한 위상정렬 과정
  1. 임의의 노드를 시작점으로 지정한다.
  2. dfs를 진행하며 노드를 방문한다.
  3. 더이상 방문할 노드가 없을 때 그 노드를 스택에 담아준고 방문 처리
  4. 이전 깊이의 노드로 돌아가 방문할 수 있는 노드가 있는지 확인
  5. 3~4번을 모든 노드를 방문할 때까지 반복
  6. 모든 노드에 방문했다면 스택에 담긴 정점들을 출력한다.
• 위상정렬과 관련된 문제

시간복잡도

• 평균 : O(n)
  • d * (N + N) = d *2 * N ⇒ O(n) // d는 큰수의 자리수
• 최악 : O(n)
• 최선 : O(n)

In-place(제자리 정렬) : NO( 정렬할 데이터의 크기 만큼의 공간이 필요함)

Stable 정렬 : YES
→ 14와 17과 같은 경우 일의자리 수 정렬에 경우 14 17로 정렬되게 된다. 이후 십의 자리는 1과 1로 똑같지만 실제 수는 14와 17 이므로 일의 자리에서 정렬했던 순서를 지켜 정렬해야 한다.

특징

• 계수정렬에서 가장 작은 수에서 가장 큰 수까지의 범위를 K라고 할때 시간복잡도가 O(n+K)이다.
• 이 때 K가 매우 큰 수를 가지게 되면 시간, 공간복잡도가 커진다는 단점을 가지고 있다.
• 이를 개선하기 위해 기수정렬을 사용한다.
• 양수, 음수, 실수가 섞여 있으면 정리할 수 없다.
• 음수가 섞여 있을 경우
• 가장 작은 음수를 양수로 만들 수 있는 수 만큼을 모든 수에 다 더하여 모든 수를 다 양수로 만든후 다시 원상복귀 시키는 방법
• 음수만 따로 빼서 정렬해서 합치는 방법
• 데이터 타입이 일정한 경우에만 가능하다.
• 비비교 정렬이다 ! (대소 비교를 하지 않는 정렬)
• 시간복잡도는 매우 빠르나 실제로는 숫자를 복사하는 과정이 많아 속도가 느리다. → 그래서 컴퓨터 보다는 일상생활에서 우편물 정렬할때와 같이 기계적으로 정리할때 많이 쓰인다.( 퀵정렬보다 빠름 )
• 퀵소트보다 좋을까?
  • 꼭 그렇지만은 않다.
  • 내부정렬이 아니다.
  • 퀵정렬이 보통 기수 정렬에 비해 캐시를 효율적으로 사용
  • 빅오의 숨은 상수 인자가 다르다.
• 가장 작은 자리수 부터 가장 큰 자리수까지 정렬하는 방식이 LSD 기수정렬(Least Significant Digit) (기본)
• 가장 큰 자리수 부터 가장 작은 자리수까지 정렬하는 방식이 MSD(Most Significant Digit)
• MSD 기수 정렬을 하기 위해서는 가장 큰 자리수를 기준으로 계수 정렬 후 같은 값을 가지는 수끼리 다시 정렬해준다. 같은 값을 가지는 묶음이 여러개가 생길 수 있으므로 그때 분할 정복을 진행 할 수 있다.