[TIL] qsort 정렬 C언어

qsort

C언어에서 제공하는 정렬 라이브러리 함수 

헤더 파일 <stdlib.h> 

qsort 함수 원형

void qsort(void *base, size_t num, size_t width, int (__cdecl *compare )(const void *, const void *));
// base 정렬할 배열의 첫번째 요소를 가리키는 포인터 
// num 배열의 요소 개수
// width 배열 요소 하나의 크기 (바이트 단위)
// (*compar) 두 값을 비교하는 함수 포인터 
// 반환값 void, 즉 반환값 없음

qsort(정렬할 배열의 주소, 요소의 개수, 요소 하나의 크기, 비교 함수);
// 예시
qsort(n, 10, sizeof(int), compare);

qsort 비교 함수 예시

int compare(const int* a, const int* b){
	return (*a - *b); // 오름차순 정렬 
    // return (*b - *a) // 내림차순 정렬 
}

 

 

1) 정렬할 자료의 자료형에 맞게 포인터 함수로 매개 변수를 받아 사용한다 

 

2) compare 함수는 두 값의 차를 반환하며, 양수를 반환하면 두 값의 위치를 바꾸고, 음수를 반환하면 위치를 바꾸지 않는다 

왼쪽의 수 a 와 오른쪽의 수 b 를 빼서 

* a 가 b 보다 크면 a-b 일 때 return 값이 양수 - 두 값의 위치를 바꿈 

* b 가 a 보다 크면 a-b 일 때 return 값이 음수 - 두 값의 위치를 그대로 둠 

qsort 구조체 사용 예시 

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

// 구조체 정의 - 이름, 나이 저장
struct Person
{
    char name[20];
    int age;
};

// 구조체 비교 함수 - qsort 함수에서 사용할 비교 함수
// 두 구조체의 나이를 비교하여 나이 오름차순으로 정렬
int compareStruct(const void *a, const void *b)
{
    // a, b 를 struct Person 타입으로 캐스팅 후 나이 비교
    return ((struct Person *)a)->age - ((struct Person *)b)->age;
}

int main()
{
    // 구조체 변수 선언 및 초기화
    struct Person people[] =
        {
            {"Bob", 35},
            {"Cindy", 20},
            {"Ariel", 15},
            {"Dave", 4},
        };

    // 배열 크기 구하기, sizeof 로 배열 전체 크기/ 개별 요소 크기
    int n = sizeof(people) / sizeof(people[0]);

    // qsort 함수를 이용해 구조체 배열을 나이 순으로 정렬
    // (정렬할 배열의 시작 주소, 배열 요소 개수, 요소 크기, 비교 함수 포인터)
    qsort(people, n, sizeof(struct Person), compareStruct);

    // 정렬 결과 출력
    printf("구조체 배열 정렬 결과 \n");
    for (int i = 0; i < n; i++)
    {
        printf("%s (%d years old)\n", people[i].name, people[i].age);
    }

    return 0;
}

구조체 배열 정렬 결과 
Dave (4 years old)
Ariel (15 years old)
Cindy (20 years old)
Bob (35 years old)

시간 복잡도 

qsort 함수는 Quick Sort 알고리즘을 기반으로 하며, 평균 시간 복잡도 O(n log n)  이다