Sorting Problem
상위 문서: 알고리즘 설계와 분석
개요
해당 문제는 알고리즘의 기본이라고 할 수 있는 정렬 알고리즘에 대해 다룬다. 정렬 알고리즘은 입력으로는 n개의 수 으로 이루어진 수열이 주어지며, 이때 출력은 해당 수열을 재배열하여 이 되도록 하는 것이다.
Importance of Sorting
정렬은 매우 단순한 작업처럼 보이지만, 이는 실제로 매우 중요한 주제이다. 그 이유는 컴퓨터가 많은 시간을 정렬에 사용하기 때문이다. 역사적으로 컴퓨터는 약 25%의 시간을 정렬 알고리즘을 수행하는데 사용한다. 이러한 이유로, 정렬은 가장 잘 연구된 문제 중 하나이다.
컴퓨터 과학에서 정렬은 수많은 알고리즘이 연구된 주제이며, 따라서 분할 정복(divide-and-conquer), 무작위화(randomized algorithms), 시간 복잡도의 하한(lower bounds) 등과 같은 많은 개념들을 정렬 알고리즘을 공부함을 통해 배울 수 있다.
또한 데이터가 정렬되어 있으면 탐색, 중복 제거, 순위 계산, 범위 질의(range query) 등이 훨씬 쉽게 해결된다. 이때 단순한 O(n2) 정렬 알고리즘은 데이터가 커지면 사용할 수 없다. 따라서 O(n log(n)) 알고리즘을 사용해야 대규모 데이터 처리를 할 수 있다. 이는 본질적으로 시간 복잡도 측면에서 O(n2)와 O(n log(n))이 매우 큰 차이를 보이기 때문이다. Figure 1은 입력의 크기가 100,000일 때 걸리는 시간이 약 1500배나 난다는 것을 보여준다.
Pragmatics of Sorting
Comparison Functions
어떤 순열을 정렬하고자 할때, 어떤 기준으로 비교하는지는 중요한 문제이다. 예를 들어 문자열 정렬은 Alphabetizing을 기준으로 이루어 진다. 또한 그 중에서도 텍스트 문자열을 정렬할 때는 단순히 글자 순서뿐 아니라 대소문자, 구두점, 띄어쓰기 등 세부 규칙이 필요하다. 예를 들어 "Big"과 "big"을 동일시 할지 말지, 혹은 "A-B"가 "A B"보다 앞에 있을지 말지이다. 즉, 정렬이 세부적으로 어떤 기준으로 정렬할 지는 두 원소를 비교하는 함수(comparison function)에 달려 있다. 이러한 비교함수는 름차순/내림차순 여부, 대소문자 무시 여부, 사전식 정렬 여부 등을 결정한다.
Equal Elements
동일한 키를 가지는 원소들을 다룰 때에는 문제가 발생할 수 있다. 정렬 과정에서 같은 값을 가지는 원소들은 정렬 후 모두 같은 위치 근처에 위치한다. 하지만 이들의 상대적인 위치가 중요한 경우가 존재한다. 예를 들어, 한 학교 내에 있는 학생들의 성명을 성씨를 기준으로 정렬하는 경우, 성은 같더라도 이름이 다른 경우가 존재하기 때문이다. 따라서 주 키(primary key)로 구분이 안 되는 경우, 2차 키(secondary key)를 이용하여 정렬을 세밀화할 수 있다. 이는 비교 함수에서 처리되어야 한다. 이떄 퀵정렬 같은 알고리즘은 동일 원소가 많을 때 성능 저하가 생길 수 있다. 따라서 동일 원소가 많으면 특별한 처리가 필요하다.
Library Functions
우리가 프로그램을 구현할 때 정렬 기능을 이용해야 한다면, 프로그래밍 언어가 제공하는 표준 정렬 함수를 사용하는 것이 권장된다. 거의 모든 현대 프로그래밍 언어는 내장 정렬 함수를 제공한다. 이는 직접 구현하는 것보다 빠르고 안전하며, 최적화도 잘 되어 있다. 예를 들어 C언어의 qsort()는 아래와 같은 함수이다.
void qsort(void *base, size_t nel, size_t width, int (*compare)(const void *, const void *));
해당 함수에서 base는 배열의 시작 주소, nel은 원소의 개수, width는 각 원소의 크기, compare는 두 원소를 비교하는 함수 포인터이다.
int intcompare(int *i, int *j) {
if (*i > *j) return 1;
if (*i < *j) return -1;
return 0;
}
위는 정수 배열을 오름차순 정렬할 때 사용하는 비교 함수입니다.
알고리즘
Selection Sort
선택 정렬(Selection Sort) 알고리즘이란 남아 있는 정렬되지 않은 원소들 중에서 가장 작은 것을 반복적으로 찾아서 배열의 정렬된 부분의 끝에 두는 것이다. 이를 C언어 코드로 표현하면 아래와 같다:
void selection_sort(item_type s[], int n) {
int i, j; /* counters */
int min; /* index of minimum */
for (i = 0; i < n; i++) {
min = i;
for (j = i + 1; j < n; j++) {
if (s[j] < s[min]) {
min = j;
}
}
swap(&s[i], &s[min]);
}
}
위 알고리즘에서 바깥쪽 for 루프는 n번 돈다. 안쪽의 루프는 바깥 루프의 인덱스가 i일 때, n−(i+1)번 돈다. 이에 따라 if 문이 실행되는 정확한 횟수는 아래와 같다.
따라서 최악의 경우(worst case) 해당 알고리즘의 시간 복잡도는 이다. 하지만 이 방식은 조금 지루하고 까다로운 방식이다. 빅 오 표기법은 오직 최대 차항의 차수에만 신경을 쓰면 되기 때문에, 바깥쪽의 루프는 n번, 안쪽의 루프도 최대 n번 돌기 때문에, 선택 정렬(selection sort)은 최악의 경우 시간이 걸린다는 것을 어렵지 않게 추론할 수 있다. 이때 해당 알고리즘은 이미 정렬돼 있든(최선), 완전히 역순이든(최악) 상관없이, 비교 횟수는 동일하므로, 임을 추론할 수 있다.
Insertion Sort
삽입 정렬(Insertion Sort)은 배열의 앞 부분이 이미 정렬되어 있다고 가정하고, 뒤에서 새 원소를 하나씩 꺼내어 알맞은 위치에 삽입하며 전체를 정렬하는 알고리즘이다. 이를 C 언어 코드로 표현하면 아래와 같다:
void insertion_sort(item_type s[], int n) {
for (i = 1; i < n; i++) {
j = i; //이번에 삽입할 원소
while ((j > 0) && (s[j] < s[j - 1])) { //s[j]가 올바른 위치에 있으면 while문 종료
swap(&s[j], &s[j - 1]); //그렇지 않으면 스왑
j = j - 1;
}
}
}
위의 코드의 시간 복잡도를 추론하기 위해서는 내부 while 루프가 얼마나 도는지를 알아야 한다. 최악의 경우에 대해서 고려한다면, 내부의 while 문은 항상 i번 돈다고 할 수 있다. 이때 i < n이고 바깥 while문은 n번 도므로, 삽입 정렬의 시간 복잡도는 이다.
