C언어 qsort, bsearch 완벽 가이드: 배열 정렬과 이진 탐색 예제

C언어 qsort, bsearch 완벽 가이드: 배열 정렬과 이진 탐색 활용법

C언어에서 대량의 데이터를 다룰 때 효율적인 정렬(Sorting)과 검색(Searching)은 프로그램 성능의 핵심입니다. C 표준 라이브러리(<stdlib.h>)는 이를 위해 qsort와 bsearch라는 강력한 함수를 제공합니다.

오늘은 이 두 함수의 기본 사용법부터 구조체 배열을 활용한 실전 예제까지 상세히 알아보겠습니다.

Generated by Gemini AI.

---

1. qsort 함수: 퀵소트 기반 정렬

qsort는 퀵소트(Quick Sort) 알고리즘을 사용하여 배열을 정렬합니다. 임베디드 시스템이나 알고리즘 문제 풀이에서 가장 흔히 사용되는 정렬 함수입니다.

qsort 함수의 프로토타입

C

 

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

• base: 정렬할 배열의 시작 주소입니다.
• num: 배열의 전체 요소 개수입니다.
• size: 요소 하나당 크기(sizeof)입니다.
• compar: 두 요소를 비교하여 정렬 순서를 결정할 함수 포인터입니다.

정수 배열 정렬 실전 예제

C

 

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

// 비교 함수: 오름차순 정렬
int compare_int(const void *a, const void *b) {
    int arg1 = *(const int *)a;
    int arg2 = *(const int *)b;
 
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
    // 간단히 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;
}

---

2. bsearch 함수: 이진 탐색을 통한 빠른 검색

bsearch는 정렬된 배열에서 특정 데이터를 찾는 이진 탐색(Binary Search) 알고리즘을 수행합니다. 시간 복잡도가 $O(\log n)$으로 매우 빠릅니다.

bsearch 함수의 프로토타입

C

 

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

• key: 찾으려는 대상의 주소입니다.
• base: 검색 대상 배열(반드시 정렬되어 있어야 함)입니다.
• compar: qsort에서 사용한 것과 동일한 로직의 비교 함수여야 합니다.

특정 값 검색 예제

C

 

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

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

int main() {
    // bsearch 사용 전 반드시 정렬되어 있어야 함
    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를 찾았습니다. 위치(포인터): %p\n", *found, (void *)found);
    } else {
        printf("%d 값을 찾을 수 없습니다.\n", key);
    }

    return 0;
}

---

3. 심화: 구조체(Struct) 배열 정렬 및 검색

실무에서는 단순 정수보다 복잡한 데이터를 다루는 경우가 많습니다. 구조체 배열을 정렬하고 검색하는 방법은 다음과 같습니다.

구조체 정렬 및 검색 코드

C

 

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

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

// 나이 기준 비교 함수
int compare_person(const void *a, const void *b) {
    Person *p1 = (Person *)a;
    Person *p2 = (Person *)b;
    return p1->age - p2->age;
}

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

    // 1. 정렬 (나이 순)
    qsort(people, people_size, sizeof(Person), compare_person);

    // 2. 검색 (나이가 25인 사람 찾기)
    int search_age = 25;
    Person key = {"", search_age};
    Person *found = (Person *)bsearch(&key, people, people_size, sizeof(Person), compare_person);

    if (found) {
        printf("검색 성공! 이름: %s, 나이: %d\n", found->name, found->age);
    }

    return 0;
}

---

💡 개발자를 위한 핵심 요약 (Key Points)

1. 정렬 필수: bsearch를 사용하기 전에 반드시 배열이 오름차순으로 정렬되어 있어야 합니다. 그렇지 않으면 잘못된 결과를 반환합니다.
2. 데이터 안정성: qsort는 'Unstable Sort'입니다. 즉, 값이 같은 요소들의 상대적 순서가 정렬 후에 바뀔 수 있음을 유의하세요.
3. 유연한 비교: 비교 함수 내부에서 void *를 실제 타입으로 적절히 캐스팅하는 것이 중요합니다.
4. 성능 최적화: 데이터 양이 많을수록 for문을 이용한 선형 탐색보다 bsearch가 압도적으로 유리합니다.

마치며

C언어 표준 라이브러리를 잘 활용하면 복잡한 알고리즘을 직접 구현하지 않고도 안전하고 빠른 프로그램을 만들 수 있습니다. 오늘 소개해드린 qsort와 bsearch를 프로젝트에 적극 활용해 보세요!

---

포스팅이 도움이 되셨다면 하트(♥)와 댓글 부탁드립니다!

임베디드 소프트웨어 및 최적화 기법에 대한 전문적인 정보는 'Coding by Head' 블로그에서 계속됩니다.

https://coding-by-head.tistory.com/