[c언어] qsort 사용하기

단순 정렬을 통해서, 주어진 배열을 오름차순 또는 내림차순으로 정렬이 가능하다.

 

그런데 왜? qsort라는 것을 사용할까?

 

라이브러리를 제공해서?, 단순 정렬대비 타이핑을 덜 할수 있어서?

 

앞서 말한 두가지 다 맞는 말이지만,  가장 큰 이유는 시간 복잡도 때문이다.

 

int형의 경우 unsigned int와 signed int로 나뉘는데 각각의 표현 가능 범위는 하기와 같다.

 

1. unsigned int : 0 ~ 4, 294, 967,295(약 42억)

 

2. signed int: -2,147,483,648 ~ 2,147,483,647(약 21억)

 

따라서 N이 100,000(10만개)만 되어도 약 49억인데 int로는 표현이 불가능하다.

 

단순 정렬의 평균 시간복잡도는 O(N^2)이며, 최악의 시간복잡도도 O(N^2)이다.

 

따라서 다른 방법을 사용하여 정렬을 해주어야하는데, 그 대안 중 하나가 qsort방식이다.

 

qsort의 사용 방법은 하기와 같다.

 

qsort(배열의 주소, 갯수, 배열의 사이즈, 비교함수)

반응형

 

 

#include<stdlib.h>

int A[10];

int comp(const (void *)a, const (void *)b)
{ 
    return *(int *)a - *(int *)b; 
    // a와 b의 type은 void *(보이드 포인터)이다.
    // comp 함수의 리턴 타입은 int이다.
    // 따라서 a와 b의 타입을 int *(인트 포인터)로 캐스팅해준다.
}

void main(void)
{
    qsort(A, N, sizeof(A[0]), comp); // qsort(정렬하려는 배열 주소, 갯수, 배열 사이즈, 비교함수)
    // 비교함수의 값은 양수 or 0 or 음수로 나오게 설계한다.
    // 양수면 배열을 오름차순으로 정렬한다.
    // 0이면 그대로 둔다.
    // 음수면 양수의 결과를 반대로 바꾼다(내림차순 정렬)
}