[ 정렬 / C언어 ] qsort 퀵 정렬.

* 코딩도장 참고함.

정렬의 종류중 퀵정렬 함수에 대해 알아볼것이다.

stdlib.h 헤더 파일에 qsort 함수가 선언되어있다.

퀵 정렬 함수에는 정렬할 배열 또느 메모리의 주소, 요소개수, 요소크기, 비교함수를 넣어준다.

- qsort(정렬할배열, 요소개수, 요소크기, 비교함수);

- qsort(정렬할메모리주소, 요소개수, 요소크기, 비교함수);

 

먼저 qsort 함수를 사용하기 전에 비교함수를 만들어야 한다.

오름차순 정렬 조건일 때는 a<b 일 때는 -1, a>b 일 때는 1, a=b 일 때는 0을 반환한다.

내림차순 정렬 조건은 오름차순 정렬 조건의 반대로 하면 된다.

 

비교 함수를 정의할 때는 반드시 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 nun2 = *(int *)b; // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    
    if (num1 < num2) return -1; // a가 b보다 작을 때 -1 반환
    
    if (num1 > num2) return 1; // a가 b보다 클 때 1 반환
    
    return 0; // a와 b가 같을 때는 0 반환
 }

* const void * 

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

 

qsort 함수 호출

qsort 함수에 정렬할 배열, 요소 개수, 요소 크기, 비교 함수를 넣어줍니다.

요소 크기는 sizeof 로 구하면 되고, 비교 함수는 괄호를 붙이지 않은 함수 포인터를 넣습니다.

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

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

 

오름차순과 내림차순을 더 간단하게 구현하는 방법 (매개변수를 뺀 값을 반환)

int compare(const void *a, const void *b
{
	return *(int *)a - *(int *)b; // 오름차순
    
    return *(int *)b - *(int *)a; // 내림차순
    
    // 값을 반환할 때 반드시 -1, 1, 0일 필요는 없음. 
    // 값이 같을 때만 0이면 되고, 값이 크거나 작을 때는 음수와 양수를 반환하면 됨.
}

 

- 퀵 정렬은 비교함수의 const void 포인터 매개변수를 다루는 방법만 기억하면 됨