DFS(Depth-First Search, 깊이 우선 탐색)과 BFS(Breadth-First Search, 너비 우선 탐색)은 그래프 탐색 시 사용되는 알고리즘이다.

각각을 자세히 설명하기 전에, 간단한 모형으로 설명하자면 다음과 같다.

시간 복잡도가 O(n^2)인 정렬은 간단하다는 장점이 있으나, 시간이 오래 걸린다는 단점을 피해갈 수 없다. 따라서 시간을 단축시키기 위해서는 시간 복잡도가 O(nlogn)인 정렬을 사용해야 한다. 본 글에서는 시간 복잡도가 O(nlogn)인 정렬로 힙 정렬, 합병 정렬을 소개한다.

시간복잡도가 O(n^2) 인 정렬에는 선택정렬, 삽입정렬, 버블정렬 등이 있다.

참고) 아래의 정렬 구현 시에는 다음과 같은 매크로를 사용하였다.
#define SWAP(x,y,temp) ( (temp)=(x), (x)=(y), (y)=(temp) )

1. 선택 정렬 (Selection Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void selection_sort(int list[], int n) {
 int i, j, min, temp;
 
 //마지막 숫자는 자동 정렬이므로 n-1번 반복
 for(i=0; i<n-1; i++) {
  min = i;
  
  //최솟값 탐색
  for(j=i+1; j<n; j++) {
   if(list[j]<list[min])
    min = j;
  }
  if(i != min) SWAP(list[i],list[min],temp);
 }
}