C 언어 내비게이터 ― 시스템 개발을 위한 최강 리소스

C 언어 qsort 함수란? 기본부터 응용까지 완전 해설 | 고속 정렬 알고리즘 활용법

표준 라이브러리 함수
目次

1. qsort 함수 개요

C 언어의 표준 라이브러리에서 제공되는qsort 함수는, 배열 내의 요소를 정렬하기 위한 강력한 도구입니다.qsort는, 퀵소트 알고리즘을 사용하여 빠르게 데이터를 정렬할 수 있으며, 매우 효율적입니다. 이 섹션에서는,qsort의 기본적인 작동 방식을 설명하고, 왜 이 함수가 중요한지 설명합니다.

qsort란?

qsort는, 배열이나 리스트 등 데이터 를, 사용자 정의 비교 함수에 기반하여 정렬하는 범용 함수입니다. C 언어의 표준 함수이며, 많은 개발 현장에서 널리 이용됩니다. 예를 들어, 정수 배열이나 문자열 배열, 더 나아가 구조체를 포함하는 데이터를 효율적으로 정렬할 수 있습니다.
#include <stdio.h>
#include <stdlib.h>

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

int main() {
    int values[] = {40, 10, 100, 90, 20, 25};
    size_t values_len = sizeof(values)/sizeof(values[0]);

    qsort(values, values_len, sizeof(int), compare);

    for(int i = 0; i < values_len; i++) {
        printf("%d ", values[i]);
    }
    return 0;
}
위 코드는, 정수 배열을qsort를 사용하여 정렬하는 기본적인 예제입니다. 여기서는, 비교 함수를 사용해 크기 관계를 판단하고, 배열의 정렬을 수행합니다.

2. qsort의 인수와 사용법

qsort의 프로토타입은 다음과 같습니다：
void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));

인수 상세

  1. base: 정렬 대상 배열의 시작 포인터.
  2. num: 배열의 요소 수.
  3. size: 각 요소의 크기(바이트 단위).
  4. compar: 비교 함수에 대한 포인터.
이 함수는 비교 함수에 기반하여 요소를 정렬합니다. compar는 두 요소를 인수로 받아 어느 것이 큰지를 반환하는 함수입니다. 이 유연성으로 다양한 데이터 타입을 정렬할 수 있습니다.

비교 함수 만들기

비교 함수는 qsort 동작의 핵심이 됩니다. 아래와 같이 요소 간 비교를 수행하는 함수를 정의합니다。
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
이 함수는 a와 b의 값을 비교하여 a가 작을 경우 음수를, 같을 경우 0을, 클 경우 양수를 반환합니다. 이를 통해 qsort는 배열을 오름차순으로 정렬합니다.

3. qsort의 내부 동작: 퀵소트 알고리즘

qsort는 퀵소트라는 알고리즘을 내부에서 사용합니다. 퀵소트는 분할 정복법을 이용한 알고리즘으로, 다음 절차에 따라 동작합니다：
  1. 피벗 선택: 배열의 중앙 근처 또는 마지막 요소를 피벗(기준)으로 선택합니다。
  2. 분할: 피벗보다 작은 요소를 왼쪽으로, 큰 요소를 오른쪽으로 이동합니다。
  3. 재귀적 정렬: 각각의 부분 배열에 대해 재귀적으로 같은 작업을 반복합니다。
이러한 분할과 통합을 반복함으로써 효율적으로 배열을 정렬합니다. 퀵소트의 평균 시간 복잡도는 O(n log n)이며, 다른 정렬 알고리즘에 비해 매우 빠릅니다. 다만, 최악의 경우(이미 정렬된 배열 등)에는 O(n^2) 가 되므로 주의가 필요합니다。

4. 비교 함수 생성 방법

qsort의 강점은, 서로 다른 데이터 타입에 대해 커스텀 비교 함수를 만들 수 있다는 점에 있습니다. 아래에, 서로 다른 데이터 타입에 대한 비교 함수 예시를 보여드립니다.

정수 비교 함수

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

문자열 비교 함수

int compare_str(const void *a, const void *b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

구조체 비교 함수

struct Person {
    int id;
    const char* name;
};

int compare_person(const void *a, const void *b) {
    return ((struct Person*)a)->id - ((struct Person*)b)->id;
}
이와 같이, qsort는 비교 함수를 커스터마이즈함으로써, 배열 내용에 맞춘 유연한 정렬이 가능합니다。

5. qsort를 이용한 구조체 배열 정렬

구조체를 포함하는 배열을 정렬할 때도, qsort는 매우 유용합니다. 예를 들어, 아래와 같은 Person 구조체 배열을 id 필드로 정렬하는 경우를 생각해 봅니다.
struct Person people[] = {
    {1, "Alice"},
    {3, "Charlie"},
    {2, "Bob"}
};

qsort(people, 3, sizeof(struct Person), compare_person);
compare_person 함수를 사용하여 id를 기준으로 정렬하면, Alice, Bob, Charlie 순으로 배열할 수 있습니다.

6. 성능 최적화와 다른 알고리즘과의 비교

퀵소트의 성능

퀵소트는 무작위 데이터를 다룰 때 매우 효율적이며 평균 O(n log n)의 시간 복잡도를 가집니다. 그러나 정렬 대상이 이미 정렬되어 있는 경우 최악의 경우 O(n^2)의 시간 복잡도가 될 가능성이 있습니다. 따라서 무작위 데이터 세트에서는 퀵소트가 유효하지만, 특정 조건에서는 다른 알고리즘을 검토하는 것이 중요합니다.

힙소트와의 비교

힙소트는 최악의 경우에도 O(n log n) 시간 복잡도를 유지하기 때문에 퀵소트보다 더 안정적인 성능을 제공합니다. 그러나 일반적으로 퀵소트가 평균적으로 더 빠르므로 무작위 데이터 세트에서는 퀵소트를 권장합니다.

머지소트와의 비교

머지소트도 O(n log n) 시간 복잡도를 가지고, 안정적인 정렬 알고리즘입니다. 머지소트는 안정성(동일한 값이 원래 순서를 유지함)을 중시하는 경우에 적합합니다. 퀵소트는 불안정한 정렬 알고리즘으로, 동일한 값의 순서를 유지하지 않지만 일반적인 용도에서는 이 차이가 문제가 되지 않는 경우가 많습니다.

7. 요약

qsort는 C 언어에서 제공되는 강력한 정렬 함수이며, 그 유연성과 고속성은 많은 프로그램에서 사용됩니다. 사용자 정의 비교 함수를 사용하면 다양한 데이터 타입 및 구조체 배열을 정렬할 수 있어 실용적인 활용 가치가 매우 높습니다. 또한, 퀵소트 알고리즘을 이해함으로써 qsort를 최대한 활용할 수 있게 됩니다. 특정 데이터 세트나 조건에 따라 힙소트나 병합소트와 같은 다른 알고리즘과 비교하여 적절한 선택을 하는 것이 성능을 최적화하는 데 중요합니다. 앞으로 실제 개발 프로젝트에서 qsort를 적절히 활용하고, 보다 효율적인 프로그램 작성에 도전해 보세요.