티스토리 뷰

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 라이브러리를 써서 정렬해보는 것이 어떨까요? ^^


댓글
  • 프로필사진 알수없음 좋은 자료 감사합니다! 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
  • 프로필사진 밥티스트 노루님 게시물을 잘 보고 있는데 문득 의문점이 드는게
    compare 함수에 strcmp 함수를 넣는게 가능하기는 하지만 매개변수가 void 형이라 char**로 형변환을 하고 대괄호에*를 넣어
    참조단계를 하나 제거해야 된다고 '데니스 리치'의 knk, 17과 q&a에 나와 있습니다.
    이 내용만 수정 가능하십니까?
    2019.08.07 22:08
댓글쓰기 폼