001. 정렬(Sorting)

정렬(sorting)은 탐색(searching)과 더불어 컴퓨터를 이용한 문제해결에있어 가장 많이 부닥치는 문제이다.
정렬은 원하는 순서대로 데이터를 배치하는 것으로,{3,4,2,2,1,10}와 같은 6개의 데이터가 있을 때 다음과 같이 정렬될 수있다.

 

• 오름차순(ascending order) 정렬: 작은 값에서 큰 값으로 배치 {1,2,2,3,4,10}
• 내림차순(descending order) 정렬: 큰 값에서 작은 값으로 배치 {10,4,3,2,2,1}

 

정렬의종류

여러 가지 정렬 방법이 있고,일반적으로 퀵정렬(QuickSort)이 가장 빠르지만, 데이터 특성에 따라(미리 어느정도 정렬되어 있다든지)다른 정렬방법이 좋은 경우도 있다.

 

• 선택 정렬(SelectionSort)
• 삽입 정렬(InsertionSort)
• 거품 정렬(BubbleSort)
• 퀵 정렬(QuickSort)
• 힙 정렬(HeapSort)
• 병합정 렬(MergeSort)
• 계수 정렬(CountingSort)
• 기수 정렬(RadixSort)

기본원리

일반적으로 정렬 알고리즘은 '비교(compare)'와 '교환(swap)'을 적절히 조합해서 이루어 진다.
(계수정렬과 기수정렬은 '비교'를 사용하지 않고, 값이 나온 회수를 이용해서 정렬한다.)

정수형인 두 값 에대해 비교하는 함수를 구현해보면 다음과 같다.

inline bool compare_asc(const int& left, const int& right) {
  return (left < right);
}

inline bool compare_dec(const int& left, const int& right) {
  return (left < right);
}

실제로 C++에 있는 sort 함수에는 정렬할 데이터를 지정하고, 비교를 할 compare 함수를 사용자가 작성하여 지정할 수도 있게 되어 있다.
즉, sort 함수 내에서 데이터에 대해 정렬을 수행하면서 두 값의 비교를 사용자가 만든 compare 함수를 이용해서 수행할 수 있게 하는 것이다.
(함수 호출을 하는 것이기에 성능이 걱정되는데, 포인터 함수 형태로 compare를 호출하기에 함수 호출에 의한 오버헤드를 최소화할 수 있다)

교환을 하는 코드를 작성해보면 다음과 같다.

inline void swap(int& left, int& right) {
  int tmp;
  tmp = left;  left = right;  right = tmp;
}

데이터의 표현

데이터의 집합을 표현하기 위해 C에서는 배열을 사용하였다.
이 배열은 다음과 같은 약점을 가지고 있어서, C++에서는 vector를 사용하는 게 좋다.
- 배열은 크기를 알지 못하는 경우가 있다. (함수에 배열을 전달했을 때)
- 배열의 크기를 동적으로 변경하기 힘들다.
따라서, 이 문서에서 정렬에 대한 코딩은 vector를 사용해서 할 것이다.

데이터의 크기, 인덱스

• 데이터의 크기는 n.
• 인덱스는 0,1, ...,(n-2),(n-1) 

다음 챕터부터는 각 정렬 방법에 대해 설명하고 코딩한다.