15 탐색과 정렬

이 장은 배열을 탐색하고 정렬하기 위한 함수들을 설명하고 있다. 당신은 배열에 있는 objects의 크기와 요소의 전체개수와 함께, 인수로써 적당한 비교 함수를 줄 수 있다.

15. 1 비교 함수 정의하기

배열을 정렬하는 라이브러리 함수를 사용하기 위해서, 당신은 어떻게 그 배열의 요소들을 비교할 것인지 알려줘야만 한다. 이것을 하기 위해, 당신은 배열의 두 개의 요소를 비교하기 위한 비교함수를 공급한다. 그 라이브러리는 비교하기 위한 두 개의 배열 요소들을 가리키는 포인터가 인수로써 주어지면, 이 함수를 호출할 것이다. 당신의 비교함수는 strcmp( 5. 5절 [String/Array Comparison] 참조)가 하는 방법으로 값을 반환하는데, 그 방법이란 첫 번째 인수가 두 번째 인수보다 작으면 음수를 반환하고, 만일 같으면 0을 반환하고, 첫 번째가 크면 양수를 반환한다. 이곳에서는 double형의 숫자들로 이루어진 배열을 가지고 작업하는 비교함수의 예가 있다.

int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}

헤더파일 'stdlib. h'는 비교함수들의 데이터 타입을 위한 이름을 정의하고 있다. 이 타입은 GNU 확장이다.

int comparison_fn_t (const void *, const void *);

15. 2 배열 탐색 함수

정렬된 배열에서 키(key)값과 같은 요소를 탐색하기 위해서는, bsearch함수를 사용하라. 이 함수를 위한 프로토타입은 헤더파일 'stdlib. h'에 있다.

함수 : void *bsearch (const void *key, const void *array, size_t count, size_t size, comparison_fn_t compare)

bsearch 함수는 key 와 동등한 오브젝트를 정렬된 배열 array에서 찾는다. 그 배열은 size 바이트의 크기를 가진, count 개의 요소를 갖는다. compare 함수는 비교를 수행하는데 사용된다. 이 함수는 두 개의 포인터 인수로 호출되고 첫 번째 인수가 두 번째 인수보다 적거나, 같거나, 또는 큼에 해당하는 정수를 반환한다. 배열의 요소들은 이 비교함수에 의하여 오름차순으로 미리 정렬되어져야만 한다.
반환값은 key값과 같은 배열의 요소를 가리키는 포인터이거나, 또는 같은 요소를 발견하지 못하면 널 포인터를 반환한다. 만일 그 배열이 key값과 같은 것을 한 개 이상 가지고 있다면, 반환된 것은 정해지지 않았다. 이 함수는 바이너리 탐색 알고리즘을 사용해서 동작한다는 것에 기인하여 bsearch라는 이름이 유래됐다.

15. 3 배열 정렬 함수

비교 함수를 사용하여 배열을 정렬하기 위해서는, qsort 함수를 사용하라. 이 함수를 위한 프로토타입은 'stdlib. h'에 있다.

함수 : void qsort (void *array, size_t count, size_t size, comparison_fn_t compare)

qsort 함수는 배열 array를 정렬한다. 그 배열은 size의 크기를 가진 count개의 요소를 갖는다. compare 함수는 배열 요소들의 비교를 수행하는데 사용된다. 이 함수는 두 개의 포인터 인수로 호출되고 첫 번째 인수가 두 번째 인수와 비교해서 큰지, 같은지, 적은지를 알 수 있는 값을 반환한다.
주의: 만일 두 개의 오브젝트가 같다면, 정렬된 후의 그들의 순서는 예측할 수 없다. 그것은 이 정렬이 안정적이지 못하다는 것을 말하고 있다. 배열의 단지 한 부분만을 가지고 비교를 할 때 두 개의 요소가 같다고 나오는 경우, 그들은 단지 key 값만 같은 뿐이지 다른 점에 있어서는 차이가 있을 것이다.

만일 당신이 안정적인 정렬을 원한다면, 당신은 두 개의 요소사이에 부족한 다른 측면의 차이나, 그들의 주소로 그들을 비교하는 것과 같은 비교 함수를 써서 이 결과를 얻을 수 있다.

이곳은 위에 정의된 비교 함수를 사용해서, 숫자 순서로 double형의 배열을 정렬하는 예를 보여주고 있다. ( 15. 1 [Comparison Functions] 참조. )

{
double *array;
int size;
. . .
qsort (array, size, sizeof (double), compare_doubles);
}

qsort 함수는 "퀵 소트(quick sort)" 알고리즘을 사용해서 동작한다는 사실에 기인하여 qsort라는 이름이 유래되었다.

15. 4 탐색과 정렬의 예

이곳에서는 구조체의 배열에 qsort 와 bsearch를 사용하는 예를 보여주고 있다. 배열의 오브젝트들은 strcmp 함수를 사용해서 그들의 이름을 비교함으로써 정렬되어졌다.

그러면, 우리는 그들의 이름에 기초한 개개의 오브젝트들을 살펴볼 수 있다.

#include <stdlib. h>
#include <stdio. h>
#include <string. h>
/* 정렬할 critter들의 배열을 정의하라. */
struct critter
{
const char *name;
const char *species;
};
struct critter muppets[] =
{
{"Kermit", "frog"},
{"Piggy", "pig"},
{"Gonzo", "whatever"},
{"Fozzie", "bear"},
{"Sam", "eagle"},
{"Robin", "frog"},
{"Animal", "animal"},
{"Camilla", "chicken"},
{"Sweetums", "monster"},
{"Dr. Strangepork", "pig"},
{"Link Hogthrob", "pig"},
{"Zoot", "human"},
{"Dr. Bunsen Honeydew", "human"},
{"Beaker", "human"},
{"Swedish Chef", "human"}
};
int count = sizeof (muppets) / sizeof (struct critter);
/* 이것은 정렬과 탐색을 위해 사용하는 비교함수이다. */
int
critter_cmp (const struct critter *c1, const struct critter *c2)
{
return strcmp (c1->name, c2->name);
}
/* critter에 대한 정보를 프린트하라. */
void
print_critter (const struct critter *c)
{
printf ("%s, the %s\n", c->name, c->species);
}
/* 정렬된 배열을 살펴보라 */
void
find_critter (const char *name)
{
struct critter target, *result;
target. name = name;
result = bsearch(&target, muppets, count, sizeof (struct critter), critter_cmp);
if (result)
print_critter (result);
else
printf ("Couldn't find %s. \n", name);
}
/* Main 함수 */
int
main (void)
{
int i;
for (i = 0; i < count; i++)
print_critter (&muppets[i]);
printf ("\n");
qsort (muppets, count, sizeof (struct critter), critter_cmp);
for (i = 0; i < count; i++)
print_critter (&muppets[i]);
printf ("\n");
find_critter ("Kermit");
find_critter ("Gonzo");
find_critter ("Janice");
return 0;
}
이 프로그램의 출력은 다음과 같다.
Kermit, the frog
Piggy, the pig
Gonzo, the whatever
Fozzie, the bear
Sam, the eagle
Robin, the frog
Animal, the animal
Camilla, the chicken
Sweetums, the monster
Dr. Strangepork, the pig
Link Hogthrob, the pig
Zoot, the human
Dr. Bunsen Honeydew, the human
Beaker, the human
Swedish Chef, the human
Animal, the animal
Beaker, the human
Camilla, the chicken
Dr. Bunsen Honeydew, the human
Dr. Strangepork, the pig
Fozzie, the bear
Gonzo, the whatever
Kermit, the frog
Link Hogthrob, the pig
Piggy, the pig
Robin, the frog
Sam, the eagle
Swedish Chef, the human
Sweetums, the monster
Zoot, the human
Kermit, the frog
Gonzo, the whatever
Couldn't find Janice.
이 게시물을...