[C언어] qsort() 함수란?

 

`qsort()` 함수는 배열의 요소들을 정렬하기 위해 사용되는 범용적인 함수이다. 표준 라이브러리 `<stdlib.h>`에 정의되어 있으며, 다양한 데이터 타입을 정렬할 수 있는 장점이 있다. 이 함수는 퀵 정렬 알고리즘을 기반으로 구현되었다.

 

사용법

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

매개변수

• `base` : 정렬할 배열의 시작 주소를 가리킨다. 이 매개변수는 배열의 첫 번째 요소를 가리키며, `void*` 타입으로 정의되어 있어 다양한 데이터 타입을 처리할 수 있다.
• `num` : 배열의 요소 개수를 나타낸다. 몇 개의 요소를 정렬할지 알려주는 역할을 한다.
• `size` : 각 요소의 크기를 바이트 단위로 나타낸다. 예를 들어, 정수 배열을 정렬하려면`sizeof(int)` 값을 넘겨주면 된다.
• `compare` : 두 요소를 비교하기 위한 함수 포인터이다. 이 함수는 정렬 방식(오름차순 또는 내림차순)을 정의한다.

 

비교 함수

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

• 비교 함수는 두 포인터를 인자로 받아야 한다.
• 반환값이 음수이면 첫 번째 인자가 두 번째 인자보다 작다는 의미이다.
• 반환값이 양수이면 첫 번째 인자가 더 크다는 의미이다.
• 반환값이 0이면 두 값이 같다는 의미이다.

 

예제

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

int compare(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);

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

이 예제에서는 compare 함수에서 두 정수를 비교하여 `qsort()`가 배열을 오름차순으로 정렬하도록 하였다. 정렬 후 배열의 요소들은 [1, 2, 5, 5, 6, 9]로 출력된다.

 

 

장점

• 범용성 :`qsort()`는 정수, 실수, 구조체 등 다양한 데이터 타입을 정렬할 수 있다. 이는`void*`를 사용하여 모든 타입을 다룰 수 있기 때문이다.
• 빠른 속도 : 평균 시간 복잡도가 \( O(n \log n) \) 으로, 대부분의 경우 매우 효율적이다.

단점

• 최악의 경우 성능 : 퀵 정렬의 특성상 최악의 경우 시간 복잡도는 \( O(n^2)\) 이 될 수 있다. 이는 이미 정렬된 배열을 다시 정렬할 때 발생할 수 있다.
• 원본 수정 :`qsort()`는 원본 배열을 직접 수정하므로, 정렬 이전의 배열이 필요하다면 별도의 복사본을 만들어야 한다.