◀ 73.1 거품 정렬 구현하기73.3 퀴즈 ▶︎

73.2 퀵 정렬 함수 사용하기

이번에는 퀵 정렬 함수를 사용해보겠습니다. 퀵 정렬 함수에는 정렬할 배열 또는 메모리의 주소, 요소 개수, 요소 크기, 비교 함수를 넣어줍니다(stdlib.h 헤더 파일에 선언되어 있습니다).

  • qsort(정렬할배열, 요소개수, 요소크기, 비교함수);
  • qsort(정렬할메모리주소, 요소개수, 요소크기, 비교함수);
    • void qsort(void *_Base, size_t _NumOfElements, size_t _SizeOfElements, int (*_PtFuncCompare)(void const *, void const *));

실제로 정렬을 한다면 정렬할 배열의 자료형도 제각각이고 비교 방식도 여러 가지겠죠? 그래서 비교 함수는 우리가 구현해서 함수의 메모리 주소(함수 포인터)를 넣어주게 됩니다.

다음 내용을 소스 코드 편집 창에 입력한 뒤 실행해보세요.

quick_sort.c

#include <stdio.h>
#include <stdlib.h>    // qsort 함수가 선언된 헤더 파일

int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2)    // a가 b보다 작을 때는
        return -1;      // -1 반환
    
    if (num1 > num2)    // a가 b보다 클 때는
        return 1;       // 1 반환
    
    return 0;    // a와 b가 같을 때는 0 반환
}

int main()
{
    int numArr[10] = { 8, 4, 2, 5, 3, 7, 10, 1, 6, 9 };    // 정렬되지 않은 배열

    // 정렬할 배열, 요소 개수, 요소 크기, 비교 함수를 넣어줌
    qsort(numArr, sizeof(numArr) / sizeof(int), sizeof(int), compare);

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", numArr[i]);    // 1 2 3 4 5 6 7 8 9 10
    }

    printf("\n");

    return 0;
}

실행 결과

1 2 3 4 5 6 7 8 9 10

먼저 qsort 함수를 사용하기 전에 비교(compare) 함수를 만들어야 합니다. 다음은 오름차순 정렬 조건입니다.

  • a < b일 때는 -1을 반환
  • a > b일 때는 1을 반환
  • a == b일 때는 0을 반환

이건 qsort를 사용하기 위한 약속입니다. 만약 a < b 일 때 1을 반환하면 반대로 내림차순 정렬이 됩니다.

비교 함수를 정의할 때는 반드시 int형 반환값과 const void 포인터 매개변수가 두 개 있어야 합니다. 하지만 const void 포인터로는 값을 비교할 수 없으므로 정렬할 배열의 자료형에 따라 const void 포인터를 변환한 뒤 역참조하여 값을 가져옵니다. 여기서는 정렬할 배열이 int형이므로 const void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져왔습니다.

값을 가져온 뒤에는 각 값을 비교하여 -1, 1, 0을 반환합니다.

int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2)    // a가 b보다 작을 때는
        return -1;      // -1 반환
    
    if (num1 > num2)    // a가 b보다 클 때는
        return 1;       // 1 반환
    
    return 0;    // a와 b가 같을 때는 0 반환
}
참고 | const void *

const void *는 void형 상수를 가리키는 포인터라는 뜻입니다. 즉, qsort 함수를 통해 compare 함수가 포인터를 전달 받았을 때 포인터가 가리키는 값이 상수입니다. 따라서  compare 함수 안에서는 값을 임의로 변경해서는 안 됩니다.

이제 qsort 함수를 호출합니다. qsort 함수에 정렬할 배열, 요소 개수, 요소 크기, 비교 함수를 넣어줍니다. 요소 크기는 sizoef로 구하면 되고, 비교 함수는 괄호를 붙이지 않은 함수 포인터를 넣습니다.

int numArr[10] = { 8, 4, 2, 5, 3, 7, 10, 1, 6, 9 };   // 정렬되지 않은 배열

// 정렬할 배열, 요소 개수, 요소 크기, 비교 함수를 넣어줌
qsort(numArr, sizeof(numArr) / sizeof(int), sizeof(int), compare);

printf로 각 요소를 출력해보면 1부터 10까지 순서대로 정렬된 것을 볼 수 있습니다.

참고 | 내림 차순

내림차순 비교 함수는 오름차순에서 부등호만 반대로 바꾸면 됩니다.

  • a > b일 때는 -1을 반환
  • a < b일 때는 1을 반환
  • a == b일 때는 0을 반환

quick_sort_descending.c

int compare(const void *a, const void *b)    // 내림차순 비교 함수 구현
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 > num2)    // a가 b보다 클 때는
        return -1;      // -1 반환
    
    if (num1 < num2)    // a가 b보다 작을 때는
        return 1;       // 1 반환
    
    return 0;           // a와 b가 같을 때는 0 반환
}

오름차순과 내림차순을 좀 더 간단하게 구현하려면 다음과 같이 매개변수를 뺀 값을 반환하면 됩니다.

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

int compare(const void *a, const void *b)
{
    return *(int *)b - *(int *)a;    // 내림차순
}

즉, 값을 반환할 때 반드시 -1, 1, 0일 필요는 없습니다. 값이 같을 때만 0이면 되고, 값이 크거나 작을 때는 음수와 양수를 반환하면 됩니다.

지금까지 배열을 정렬하는 방법을 배웠습니다. 거품 정렬은 직접 구현을 하다 보니 내용이 다소 어려웠습니다. 당장은 내용을 완벽히 이해하지 않아도 되며 나중에 거품 정렬이 필요할 때 다시 돌아와서 찾아보면 됩니다. 그리고 퀵 정렬은 비교 함수의 const void 포인터 매개변수를 다루는 방법만 기억하면 됩니다.


◀ 73.1 거품 정렬 구현하기73.3 퀴즈 ▶︎