15 탐색과 정렬
이 장은 배열을 탐색하고 정렬하기 위한 함수들을 설명하고 있다. 당신은 배열에 있는 objects의 크기와
요소의 전체개수와 함께, 인수로써 적당한 비교 함수를 줄 수 있다.
배열을 정렬하는 라이브러리 함수를 사용하기 위해서, 당신은 어떻게 그 배열의 요소들을 비교할 것인지
알려줘야만 한다. 이것을 하기 위해, 당신은 배열의 두 개의 요소를 비교하기 위한 비교함수를 공급한다.
그 라이브러리는 비교하기 위한 두 개의 배열 요소들을 가리키는 포인터가 인수로써 주어지면, 이 함수를
호출할 것이다. 당신의 비교함수는 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 *);
정렬된 배열에서 키(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라는 이름이 유래됐다.
비교 함수를 사용하여 배열을 정렬하기 위해서는, 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라는 이름이
유래되었다.
이곳에서는 구조체의 배열에 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.
목차 이전 : 14. 저수준 연산함수들 다음 : 16. 패턴 매칭