kruskal 알고리즘은 최소 신장 트리 (Minimum Spanning Tree,MST)를 구하는 알고리즘으로, 그리디 알고리즘에 속한다

위상정렬 (Topological sort) 는 cycle이 없는 방향 그래프(Directed Acyclic Graph,DAG) 에서 정점들을 선형순서(간선의 방향을 거스리지 않도록)로 나열하는 것을 의미하며, 주어진 그래프내에서 여러 개의 위상 정렬 결과가 나올수도 있다.

대표적으로 위상정렬을 이용하는 예로 대학교 선수과목 수강 순서를 정할떄 이용할 수 있다.

위상 정렬 알고리즘의 수행과정은 다음과 같다.

1. 그래프에서 진입 차수가 0 인 정점 v 를 출력하고, v와 연결된 간선을 제거한다.
2. 다시 1번 과정을 거치며, 진입 차수가 0인 정점을 찾는다.

Quick sort는 기준 데이터인 pivot 을 설정하고, pivot보다 작은 값과 pivot보다 큰 값의 위치를 교환하고, 두 개의 포인터가 어긋나는 시점에 왼쪽에 위치한 포인터를 pivot과 교환해줌으로서, pivot의 왼쪽에는 pivot보다 작은 값들만 , pivot의 오른쪽에는 pivot보다 큰 값들만 위치하도록 한다.
pivot의 왼쪽, 오른쪽 부분의 배열에 대해서 다시 재귀적으로 정렬을 수행하는 정렬 알고리즘이다.

플루이드의 토끼와 거북이 알고리즘은 Linked List에서 cycle 존재 유무와 cycle의 길이 및 , 시작점 을 확인할 수 있는 알고리즘으로 2개의 다른 속도로 움직이는 포인터를 사용한다. , (알고리즘 이름이 왜 토끼와 거북이인지 알 것 같다)

알고리즘은 크게 2 phase로 나뉜다.

Phase 1. 다른 속도로 움직이는 두 pointer의 교차점을 찾고,
Phase 2. cycle의 진입로를 찾는다.

먼저 phase 1을 세부적으로 살펴보면,

merge sort(합병정렬) 은 크기가 N인 입력을 1/n 크기로 분할하고, 각각에 대해 재귀적으로 다시 합병정렬을 수행한 후,n개의 정렬된 부분은 합병하는 정렬 알고리즘이다.