[C 언어] 퀵소트(qsort)를 이용한 배열, 구조체 정렬 사용 예시 (example code)

 

 

안녕하세요,

 

오늘은 표준 라이브러리인 퀵소트 함수 qsort 사용 예시에 대해 포스팅 해보도록 하겠습니다.

 

 

퀵소트는 평균적으로 O(nlogn)의 시간복잡도를 갖는 매우 효율적인 알고리즘입니다. 직접 구현하기는 까다롭지만 라이브러리를 제공하기 때문에 사용하기 무척 편리합니다.

 

qsort를 사용하기 위해서는 C 에서는 stdlib.h, C++에서는 cstdlib 헤더 파일을 포함(include) 해야 합니다.

 

C 언어 기준으로 예제 코드 및 결과를 작성해보도록 하겠습니다.

 

 

배열 정렬하기

 

위의 코드는 오름차순 기준으로 작성한 코드입니다.

 

내림차순으로 하려면 cmpfunc 함수에서 return을 (*(int *)b - *(int *)a); 로 하면 됩니다.

#include <stdio.h>

#include <stdlib.h> // to use qsort

// comapre function prototype

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

int main(void)

{

    int arr_count = 5;

    int arr[5] = {5, 3, 1, 4, 2};

    printf("Before sorting the array\n");

    for (int i = 0; i < arr_count; i++)

    {

        printf("%d ", arr[i]);

    }

    printf("\n");

    // array, array_size, element_size, compare function pointer

    qsort((int *)arr, arr_count, sizeof(int), cmpfunc);

    printf("After sorting the array\n");

    for (int i = 0; i < arr_count; i++)

    {

        printf("%d ", arr[i]);

    }

    return 0;

}

// compare function for integer array

int cmpfunc(const void *a, const void *b)

{

    return (*(int *)a - *(int *)b);

}

 

결과

Before sorting the array
5 3 1 4 2
After sorting the array
1 2 3 4 5

 

반응형

 

구조체 배열 정렬하기

 

이번에는 구조체 배열을 정렬해보도록 하겠습니다. 

 

비교함수인 cmpfunc 안에서 정렬하고자 하는 멤버 변수를 이용해 return을 구성하면 됩니다.

 

string 타입의 멤버 변수를 이용해 정렬하려면 strcmp 함수를 이용하면 됩니다.

(return 음수 if string1 < string2, return 0 if string1 == string2, return 양수 if string1 > string2)

 

해당 함수를 사용하기 위해서는 string.h (c++ 에서는 cstring)을 포함(include) 해야 합니다.

#include <stdio.h>

#include <string.h> // to use strcmp

#include <stdlib.h> // to use qsort

typedef struct

{

    char name[10];

    int age;

} Student_t;

// comapre function prototype

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

int main(void)

{

    int arr_count = 5;

    Student_t student[5] = {{"bb", 15}, {"ab", 11}, {"aa", 12}, {"ba", 19}, {"ca", 13}};

    printf("Before sorting the array\n");

    for (int i = 0; i < arr_count; i++)

    {

        printf("%s %d\n", student[i].name, student[i].age);

    }

    printf("\n");

    // array, array_size, element_size, compare function pointer

    qsort((Student_t *)student, arr_count, sizeof(Student_t), cmpfunc);

    printf("After sorting the array\n");

    for (int i = 0; i < arr_count; i++)

    {

        printf("%s %d\n", student[i].name, student[i].age);

    }

    return 0;

}

// compare function for structure array

int cmpfunc(const void *a, const void *b)

{

    return strcmp(((Student_t *)a)->name, ((Student_t *)b)->name);

}

 

결과

Before sorting the array
bb 15
ab 11
aa 12
ba 19
ca 13

After sorting the array
aa 12
ab 11
ba 19
bb 15
ca 13

 

이름을 알파벳 반대 순으로 정렬하려면 strcmp의 인자를 반대로, 또 나이 순으로 정렬하려면 name 멤버 변수가 아닌 age 멤버 변수를 이용하면 됩니다.

 

 

지금까지 qsort 함수를 이용한 배열, 구조체 정렬 예시였습니다.

 

읽어주셔서 감사합니다.