티스토리 뷰

C, C++/C, C++

C언어 qsort() 함수

norux 2014.01.02 02:47

C언어 qsort() 함수

C언어에서는 Quick sort를 손쉽게 사용할 수 있도록 라이브러리가 구현되어 있습니다.


함수의 프로토타입은 다음과 같습니다.

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *)
  • 함수명 : qsort
  • 필요헤더 : stdlib.h
  • 리턴타입 : void
  • 파라미터 :
    1. 정렬 할 배열
    2. 배열의 총 엘리먼트 개수
    3. 배열 한 개의 크기
    4. 비교를 수행할 함수의 포인터
  • 리턴값 : 없음
  • 함수역할 : 퀵 소트(Quick sort)를 이용하여 배열을 정렬한다.

헤더파일 stdlib.h가 미리 선언되 있어야 하구요. 참고로 void * 라는 것은 어떠한 타입이든 상관없이 포인터를 받을 수 있다는 의미입니다. 즉, int 형 포인터이거나 char형 포인터이거나 구분않고 사용할 수 있습니다.


파라미터의 각 의미는 위의 설명을 참조하시면 되구요. 마지막 compare라는 함수 포인터에 대하여 값을 비교하는 함수 하나를 만들어 주어야 합니다. 이 함수가 반환되는 값에 따라 오름차순의 정렬 방법을 사용할 것인가, 내림차순의 정렬 방법을 사용할 것인가도 결정할 수 있습니다.

함수포인터에 관한 포스팅을 보고 싶으시면 이곳을 클릭 하세요


이 compare함수는 문자열비교함수인 strcmp와 같은 모양을 띄고 있습니다. 따라서 문자열의 배열이라면, strcmpy 함수를 그대로 넣어 사용할 수도 있습니다. 오름차순으로 정렬하고 싶을 때, compare함수의 첫 번째 파라미터가 더 클 때 양수를 반환, 첫 번째 파라미터가 더 작을 때 음수를 반환, 같을 때 0을 반환하게 만들면 됩니다. (내림차순일때는 반대로)


다음의 예제를 한 번 보시겠습니다.

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

// 오름차순
int compare (void *first, void *second)
{
    if (*(int*)first > *(int*)second)
        return 1;
    else if (*(int*)first < *(int*)second)
        return -1;
    else 
        return 0;
}

int main(int argc, char** argv)
{
    int arr[] = {4,3,1,7,5,9,8,2,6};
    int arr_size = sizeof(arr) / sizeof(int);
    int i;

    // before sort
    for (i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    // apply quick sort
    qsort(arr, arr_size, sizeof(int), compare);

    // after sort
    for (i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

실생활에서 가장 빠르다고 여겨지는 Quick sort, 구현이 다소 어렵다는 단점이 있지만 이미 만들어진 라이브러리를 사용함으로써 쉽게 이용할 수 있게 됩니다. 앞으로는 bubble sort를 만들어서 정렬하는 것 보다 qsort 라이브러리를 써서 정렬해보는 것이 어떨까요? ^^

신고

댓글
  • 프로필사진 doctorshin99 int compare (void *first, void *second); 가 아닌
    int compare (const void *first, const void *second); 가 더욱 좋다고 생각됩니다

    C++ 언어는 C보다 자료형과 키워드 검사에 엄격하더군요
    Dev-C++에선 const ### 형과 ### 형은 다른거라면서 컴파일 오류 띄웁니다
    2014.09.14 21:46 신고
  • 프로필사진 norux 좋은 지적 감사드립니다 ^^
    예제를 만들다보면 단순 컴파일 확인만 하다보니 놓쳐지는 부분들이 있네요.

    말씀주신대로 위에 제가 적어둔 원형대로 파라미터를 쓰는 것이 제일 좋습니다.
    원형을 보자니 두번째 파라미터 nel도 size_t 이네요.
    size_t는 unsigned int형이니 본 코드는 오버플로우의 위험성을 가지고 있네요.

    감사합니다
    2014.09.16 23:30 신고
  • 프로필사진 알수없음 좋은 자료 감사합니다! 2016.04.03 18:36 신고
  • 프로필사진 c초보 안녕하세요 c언어 초보입니다.
    끝에 strcmp로넣게되면 오름 , 내림차순 어떻게 바꿔줄수있나요 ?
    2017.07.31 00:26 신고
  • 프로필사진 c초보 2차원배열로

    홍길동
    임꺽정
    시라소니

    이렇게 있을경우
    정렬 가능한가요 ?
    2017.07.31 01:05 신고
  • 프로필사진 norux 물론 가능하지요.

    https://stackoverflow.com/a/14993508/5880860
    이 코드를 참조하시면 될 것 같습니다.
    2017.07.31 12:54 신고
  • 프로필사진 방문객 잘 봤습니다. 알아보기 쉽게 잘쓰셨네요 2017.09.27 23:22 신고
댓글쓰기 폼