[C] C언어에서 qsort 사용하기

C언어의 stdlib.h에서 제공하는 정렬함수인 qsort를 사용해보자

환경

• C언어 및 컴파일러

Quick Sort란?

원리

• pivot을 정하고 pivot보다 작은 값들을 pivot의 왼쪽 pivot보다 큰 값들은 pivot의 오른쪽으로 위치시키고 pivot의 왼쪽 값들과 오른쪽 값들을 각각 따로 또 재귀를 통해 분할정복한다.

특징

• O(nlogn)의 성능을 보이는 정렬 알고리즘중에 하나로 최악에는 O(n^2)의 성능을 보이지만 일반적으로 빠른 성능을 나타내기에 보편적으로 많이 쓰는 알고리즘 입니다.
• Divide and Conquer이라는 분할정복 방법으로 정렬을 진행하며 자세한 부분은 다음을 참고하시면 좋습니다.
• in-place sorting: 정렬 할 원소들을 위한 추가적인 메모리를 사용하지 않고 현재 메모리에서 정렬을 진행

C에서 Quick Sort인 qsort함수 사용하기

기본 구조

기본적으로 stdlib.h에서 Quick Sort 함수인 qsort 함수를 제공해주며 아래와 같습니다.

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *);

• base: 정렬하고자 하는 배열의 포인터입니다.
• nel: 배열의 각 원소들의 총 수입니다.
• width: 배열에서 원소 하나의 크기입니다.
• (*compare): 비교를 수행할 함수 포인터입니다. C언어에서는 함수를 선언하고 구현한 후에 다음처럼 포인터로 특정 함수를 지정할 수 있습니다.

비교 함수에 대해서

4번째 인자에 대해서 조금 더 자세히 설명하면 비교함수 내부에는 1, 0 , -1중에 하나를 반환해야합니다. 만약 오름차순으로 정렬을 하고 싶다면 비교함수 내부에서 첫번째 변수가 두번쨰 변수보다 클 때 1을 첫번째 변수가 두번째 변수보다 작을 때 -1을 같을 때 0을 반환하도록 작성하면 됩니다. 물론 내림차순의 경우 1과 -1을 반환하는 부분의 등호를 바꾸어주면됩니다.

예제 코드

예제 코드는 아래와 같습니다.

HelloWorld.c

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

// 오름차순으로 정렬할 때 사용하는 비교함수
int static compare (const void* first, const void* second)
{
    if (*(int*)first > *(int*)second)
        return 1;
    else if (*(int*)first < *(int*)second)
        return -1;
    else
        return 0;
}

int main()
{
    int arr[] = {32, 11, 97, 42, 21, 70, 56, 67, 88, 100};
    int array_size = sizeof(arr) / sizeof(int);
    int i;

    // 정렬 전
    for (i = 0; i < array_size; i++) printf("%d ", arr[i]);
    printf("\n");

    qsort(arr, array_size, sizeof(int), compare);

    // 정렬 후
    for (i = 0; i < array_size; i++) printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

결과는 아래와 같습니다.

참고자료

• https://en.wikipedia.org/wiki/Quicksort