[ 자료구조 ] 정렬 - 05 . qsort

[ qsort 함수 ]

[ 퀵 정렬 ]
c언어의 표준 라이브러리에 (stdlib.h) 퀵 정렬 알고리즘이 구현된 함수가 제공된다 .
qsort()함수는 다음과 같은 원형을 가지고 있다 .

void qsort(
	void*base,	//데이터 집합 배열의 주소
    size_t num,	//데이터 요소의 개수
    size_t width,//한 데이터 요소의 크기
    int (_cdecl*compare)(const void*,const void*)	//비교 함수에 대한 포인터
};

• 첫번째 매개변수 base는 데이터 집합 배열의 주소를 가리키는 포인터이다 .
• 두번째 매개변수 num은 데이터 집합 요소의 개수 (집합의 크기)이다.
• 세번째 매개변수 width는 데이터 요소 하나의 크기(바이트 단위)이다.
• 비교 수행한 결과를 반환하는 함수에 대한 포인터이다 .해당 포인터가 가리키는 함수는 다음과 같은 원형을 가진다 .

int compare((void*)&elem1 , (void*)&elem2)

비교함수는 elem1이 elem2보다 크다면 0보다 큰 수를 / 작다면 0보다 작은 수를 / 같다면 1을 반환한다 . 예는 다음과 같다.

int CompareScore(const void* _elem1 , const void* _elem2)
{
	int* elem1=(int*)_elem1;
	int* elem2=(int*)_elem2;
    
    if(*elem1 > *elem2 )
    return 1;
    else if (*elem1 == *elem2 )
    return 0;
     else if (*elem1 < *elem2 )
    return -1;
    
}

[ 함수 포인터 ]
변수 / 상수 / 함수 모두 메모리에 존재한다 . 따라서 함수에 대한 포인터가 있다면 해당 포인터가 가리키고 있는 메모리에
위치한 함수를 실행 시킬 수 있다 .

대게 어떤 함수가 외부에 있는 함수를 호출하기 위해서는 호출되는 함수가 미리 구현되어 있어야 하지만 , 함수 포인터를 이용하여 호출하는 경우에는 함수의 구현을 미리 알지 않아도 된다 .

또한 다음과 같이 동작하는 함수를 중복으로 만드는게 아닌 함수 포인터 처리를 할 수 있다 .

//내부에서 B함수를 호출
void FunctionA()
{
	int a = FunctionB();
}

//포인터를 사용하면 B,C모두 하나의 함수에서 호출이 가능하다
void FunctionA( (int*)pFunction() )
{
	int a = (*pFunction)()
}

//B , C 모두 호출이 가능하다

FunctionA(&FunctionB);
FunctionA(&FunctionC);

[ qsort 함수 테스트 ]

[ qsort.cpp ]

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

int CompareScore(const void* _elem1, const void* _elem2)
{
	int* elem1 = (int*)_elem1;
	int* elem2 = (int*)_elem2;

	if (*elem1 > *elem2)
		return 1;
	else if (*elem1 < *elem2)
		return -1;
	else
		return 0;
}

int main(void)
{
	int DataSet[] = { 6,5,4,3,2,1 };
	int Length = sizeof DataSet / sizeof DataSet[0];
	int i = 0;

	qsort(DataSet, Length, sizeof(int), CompareScore);

	for (i = 0; i < Length; i++)
	{
		printf("%d", DataSet[i]);
	}
	printf("\n");
	return 0;
}