C 표준 라이브러리 qsort() (feat. 퀵 정렬)

C 표준 라이브러리의 qsort 함수는 일반화된 정렬 함수로, 다양한 데이터 타입과 정렬 기준에 따라 데이터를 정렬할 수 있습니다. qsort는 이름에서 알 수 있듯이 내부적으로 퀵 정렬(Quick Sort) 알고리즘을 기반으로 동작합니다.

---

qsort 함수 정의

qsort 함수는 다음과 같이 선언되어 있습니다.

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

매개변수 설명

1. base: 정렬할 배열의 시작 주소입니다.
2. nitems: 배열의 요소 개수입니다.
3. size: 배열의 각 요소 크기(바이트 단위)입니다.
4. compar: 두 요소를 비교하는 사용자 정의 함수입니다.

---

비교 함수 정의

qsort 함수에서 중요한 역할을 하는 것이 비교 함수입니다.
비교 함수는 다음과 같은 형태로 작성됩니다:

int compare(const void *a, const void *b);

반환값

• 음수(-): a가 b보다 작음 (오름차순 정렬 시 a가 먼저 나옴).
• 0: a와 b가 같음.
• 양수(+): a가 b보다 큼 (오름차순 정렬 시 b가 먼저 나옴).

---

예제 1: 정수 배열 정렬

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

// 비교 함수 (오름차순)
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr[] = {32, 45, 17, 23, 99, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // qsort 호출
    qsort(arr, n, sizeof(int), compare);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

동작 과정

1. qsort는 배열 arr의 포인터, 요소 개수, 요소 크기, 비교 함수를 인수로 받습니다.
2. 비교 함수 compare를 사용하여 두 값을 비교하며 정렬합니다.
3. 정렬 후 배열이 오름차순으로 출력됩니다.

---

예제 2: 내림차순 정렬

오름차순 정렬 대신 내림차순으로 정렬하려면 비교 함수의 반환값을 반대로 설정합니다.

// 비교 함수 (내림차순)
int compareDescending(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

qsort 호출 시 위 함수를 전달하면 내림차순 정렬이 됩니다.

---

예제 3: 문자열 배열 정렬

qsort는 문자열 배열도 정렬할 수 있습니다.

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

// 문자열 비교 함수 (오름차순)
int compareStrings(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

int main() {
    const char *arr[] = {"banana", "apple", "cherry", "blueberry"};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%s ", arr[i]);
    }
    printf("\n");

    // qsort 호출
    qsort(arr, n, sizeof(const char *), compareStrings);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%s ", arr[i]);
    }
    printf("\n");

    return 0;
}

문자열 정렬의 특징

• strcmp 함수를 사용하여 두 문자열의 사전순서(lexicographical order)를 비교합니다.
• 문자열 배열이 오름차순으로 정렬됩니다.

---

예제 4: 구조체 배열 정렬

qsort는 구조체 배열도 정렬할 수 있습니다.
다음은 학생 정보를 정렬하는 예제입니다.

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

// 학생 구조체
typedef struct {
    char name[20];
    int score;
} Student;

// 점수 기준 비교 함수 (내림차순)
int compareStudents(const void *a, const void *b) {
    return ((Student *)b)->score - ((Student *)a)->score;
}

void printStudents(Student arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%s: %d\n", arr[i].name, arr[i].score);
    }
}

int main() {
    Student students[] = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"David", 90}
    };
    int n = sizeof(students) / sizeof(students[0]);

    printf("Original students:\n");
    printStudents(students, n);

    // qsort 호출
    qsort(students, n, sizeof(Student), compareStudents);

    printf("\nSorted students by score:\n");
    printStudents(students, n);

    return 0;
}

동작 과정

1. 구조체 배열 students를 정렬합니다.
2. compareStudents 함수는 두 학생의 점수를 비교하여 내림차순 정렬합니다.
3. 정렬 후 점수가 높은 순서대로 출력됩니다.

---

qsort의 장점

1. 범용성: 다양한 데이터 타입과 구조를 정렬할 수 있습니다.
2. 유연성: 사용자 정의 비교 함수를 통해 정렬 기준을 자유롭게 설정할 수 있습니다.
3. 효율성: 퀵 정렬 기반으로 평균 O(n log n)의 시간 복잡도를 가집니다.

---

주의 사항

1. 정렬 안정성:
   qsort는 안정적인 정렬(같은 값의 상대 순서가 유지되는 정렬)을 보장하지 않습니다.
2. 최악의 시간 복잡도:
   특정 입력에서 최악의 경우 O(n²) 시간 복잡도를 가질 수 있습니다.
3. 비교 함수의 정확성:
   비교 함수가 잘못 정의되면 qsort는 예상치 못한 결과를 초래할 수 있습니다.

---

qsort는 C 언어에서 범용적이고 효율적으로 정렬을 수행할 수 있는 강력한 도구입니다. 프로젝트에서 다양한 데이터 정렬이 필요할 때, qsort를 적절히 활용해 보세요! 😊

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.