[ 자료구조 ] 정렬 – 04 . 퀵

(정렬 기능)

(빠른 다양성)

표준 C 언어 라이브러리(stdlib.h)에 퀵 정렬 알고리즘을 구현하는 함수가 제공됩니다.

qsort() 함수에는 다음 프로토타입이 있습니다.

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

• 첫 번째 매개변수 base는 레코드 배열의 주소에 대한 포인터입니다.
• 두 번째 매개변수 num은 레코드 요소의 수(레코드 크기)입니다.
• 세 번째 매개변수 너비는 데이터 항목의 크기(바이트)입니다.
• 비교 결과를 반환하는 함수에 대한 포인터이며 포인터가 가리키는 함수는 다음과 같은 프로토타입을 가집니다.

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;
}