C qsort와 bsearch를 활용한 정렬 및 검색

C qsort와 bsearch를 활용한 정렬 및 검색

C 언어의 표준 라이브러리에는 배열을 정렬하고 검색하는 데 유용한 qsort와 bsearch 함수가 포함되어 있습니다. 이 글에서는 qsort를 이용한 정렬과 bsearch를 활용한 검색 방법을 살펴보고, 다양한 예제 코드를 통해 이를 실용적으로 활용하는 방법을 알아보겠습니다.

1. qsort 함수 개요

qsort는 C 표준 라이브러리 <stdlib.h>에 정의된 함수로, 일반적인 퀵소트(Quick Sort) 알고리즘을 기반으로 동작합니다.

qsort 함수의 프로토타입

void qsort(void *base, size_t num, size_t size,
           int (*compar)(const void *, const void *));

• base : 정렬할 배열의 시작 주소
• num : 배열의 요소 개수
• size : 배열 요소 하나의 크기 (바이트 단위)
• compar : 두 요소를 비교하는 함수 포인터

정수 배열 정렬 예제

#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    size_t arr_size = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, arr_size, sizeof(int), compare_int);

    printf("정렬된 배열: ");
    for (size_t i = 0; i < arr_size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

위 예제에서는 compare_int 함수를 사용하여 두 정수를 비교하고, qsort를 이용해 오름차순 정렬을 수행합니다.

2. bsearch 함수 개요

bsearch는 정렬된 배열에서 이진 탐색(Binary Search)을 수행하는 함수입니다.

bsearch 함수의 프로토타입

void *bsearch(const void *key, const void *base, size_t num, 
              size_t size, int (*compar)(const void *, const void *));

• key : 찾고자 하는 값의 포인터
• base : 검색할 정렬된 배열의 시작 주소
• num : 배열의 요소 개수
• size : 배열 요소 하나의 크기
• compar : 두 요소를 비교하는 함수 포인터

정렬된 배열에서 특정 값 검색 예제

#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr[] = {1, 2, 5, 5, 6, 9};
    size_t arr_size = sizeof(arr) / sizeof(arr[0]);
    int key = 5;

    int *found = (int *)bsearch(&key, arr, arr_size, sizeof(int), compare_int);

    if (found) {
        printf("%d 값을 찾았습니다!\n", *found);
    } else {
        printf("%d 값을 찾을 수 없습니다.\n", key);
    }

    return 0;
}

위 예제에서는 정렬된 배열에서 특정 정수를 찾기 위해 bsearch를 사용하였습니다. key 값이 배열에 존재하면 해당 값의 주소를 반환하며, 존재하지 않으면 NULL을 반환합니다.

3. 구조체 배열 정렬 및 검색

구조체 배열을 정렬하는 예제

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char name[20];
    int age;
} Person;

int compare_person(const void *a, const void *b) {
    return ((Person *)a)->age - ((Person *)b)->age;
}

int main() {
    Person people[] = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 22},
    };
    size_t people_size = sizeof(people) / sizeof(people[0]);

    qsort(people, people_size, sizeof(Person), compare_person);

    printf("정렬된 사람 목록: \n");
    for (size_t i = 0; i < people_size; i++) {
        printf("이름: %s, 나이: %d\n", people[i].name, people[i].age);
    }

    return 0;
}

위 예제에서는 Person 구조체 배열을 나이를 기준으로 정렬하였습니다.

구조체 배열에서 특정 값 검색 예제

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char name[20];
    int age;
} Person;

int compare_person(const void *a, const void *b) {
    return ((Person *)a)->age - ((Person *)b)->age;
}

int main() {
    Person people[] = {
        {"Charlie", 22},
        {"Alice", 25},
        {"Bob", 30},
    };
    size_t people_size = sizeof(people) / sizeof(people[0]);
    int search_age = 25;

    Person key = {"", search_age};
    Person *found = (Person *)bsearch(&key, people, people_size, sizeof(Person), compare_person);

    if (found) {
        printf("나이 %d인 사람: %s\n", found->age, found->name);
    } else {
        printf("나이 %d인 사람을 찾을 수 없습니다.\n", search_age);
    }

    return 0;
}

이 예제에서는 나이를 기준으로 bsearch를 이용하여 특정 나이의 사람을 검색하였습니다.

4. 결론

C 언어의 qsort와 bsearch는 배열을 정렬하고 검색하는 강력한 기능을 제공합니다.

• qsort를 사용하여 배열을 정렬할 때는 비교 함수가 중요하며, 데이터 유형에 따라 적절한 비교 함수를 정의해야 합니다.
• bsearch를 사용할 때는 배열이 반드시 정렬되어 있어야 하며, 같은 비교 함수를 사용해야 합니다.

위 예제들을 활용하면 다양한 상황에서 효율적으로 정렬과 검색을 수행할 수 있습니다. 프로그램에서 빠른 탐색이 필요하다면 정렬 후 이진 탐색을 적극 활용해 보세요!