qsort 함수

qsort 함수는 C 표준 라이브러리에 포함된 정렬 함수로서,  Quick sort의 'Quick' 이라는 단어에서도 알 수 있듯이 무언가를 빠르게 정렬할 수 있는 알고리즘인데 퀵 소트의 작동 원리는 마치 몇 개의 숫자 카드를 가지고 있고 이를 크기 순으로 정렬하는 것과 같다. 

첫 번째 단계에서, 하나의 카드를 뽑아 기준으로 삼는다. (이것이 피벗 즉 기준점이다.)

이제 나머지 카드를 기준 카드와 비교한다. 더 작은 카드는 왼쪽에, 더 큰 카드는 오른쪽에 놓는다. 

왼쪽과 오른쪽에 있는 카드들 역시 같은 방법으로 다시 정렬하는데, 이 과정을 계속 반복하면, 모든 카드가 크기 순서대로 정렬된다.

 

qsort 함수의 선언:
qsort 함수는 <stdlib.h> 헤더 파일에 선언되어 있고 함수 원형은 다음과 같다.

void qsort(정렬할 배열의 시작주소, 배열 원소의 개수, 배열 각 원소의 크기, int (*compare)(const void*, const void*));

여기에서 함수 원형의 맨 끝에 있는 compare는 비교 함수의 포인터이다. 이 함수는 카드를 크기 순으로 왼쪽 혹은 오른쪽에 정렬하듯이, 두 원소를 비교하여 그 결과에 따라 정렬 순서를 결정한다.

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

 

이 비교 함수는 두 개의 값을 비교하야:

• 첫 번째 값이 두 번째 값보다 작으면 음수를 반환하고
• 첫 번째 값이 두 번째 값보다 크면 양수를 반환한며
• 두 값이 같으면 0을 반환한다. 

여기서 void*는 아무것도 가리키지 않는 포인터인데, 즉 포인터의 타입을 명시하지 않는 일반적인 포인터 타입이다.

이는 이 함수가 다양한 타입의 데이터와 함께 사용할 수 있도록 유연하게 설계되었기 때문이다. 

 

참고로 compare 함수에서 *a는 메모리 주소를 저장하는 변수이다. 예를 들어서 'void* a' 라고 하면 

a는 void 타입의 포인터가 가리키는 메모리 주소를 저장하고 있는 것이다. 

int x = 10;
void* a = &x;

// 올바른 방법: void*를 적절한 타입으로 캐스팅한 후 역참조
int value = *(int*)a;  // 이 경우 x의 값을 가져옵니다 (10)
printf("%d\n", value);  // 10 출력

 

그래서 (void*)a 를 출력하면  0x7ffeefbff5c8 처럼 16 진수의 주소 값이 출력 되고

타입캐스팅 후 역참조를 한 *(int*)a 를 출력하면 실제 메모리 안에 저장된 값인 10을 출력한다. 

 

또한 비교 함수는 두 개의 const void* 타입 매개변수를 받아서 비교하고, 그 비교 결과에 따라 음수, 0, 또는 양수 중 하나를 반환한다. 

반환 값에 따른 배열 이동: 

- 음수를 반환할 때: 첫 번째 인자가 두 번째 인자보다 "작다"고 간주한다. 이는 첫 번째 인자가 두 번째 인자보다 앞에 위치해야 함을 의미한다.
- 양수를 반환할 때: 첫 번째 인자가 두 번째 인자보다 "크다"고 간주한다. 이는 첫 번째 인자가 두 번째 인자보다 뒤에 위치해야 함을 의미한다.
- 0을 반환할 때: 두 인자가 같다고 간주하고 위치 변경이 이루어지지 않는다. 

 

qsort 사용 예:

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

int compare(const void* a, const void* b) { //오름차 순으로 정렬 
return (*(int*)a - *(int*)b); } 

int main() {
	int arr[] = {4, 2, 5, 3, 1}; 
	int arr_size = sizeof(arr) / sizeof(arr[0]); 
	qsort(arr, arr_size, sizeof(int), compare); 

	for (int i = 0; i < arr_size; i++) { 
		printf("%d ", arr[i]); 
		} 
return 0; 
}

이 예제에서는 정수 배열을 오름차순으로 정렬한다. (내림차순으로 정렬하려면 상수 a와 b의 위치를 변경하면 된다.)  compare 함수는 두 정수를 비교하고, 첫 번째 정수가 두 번째 정수보다 작으면 음수를, 같으면 0을, 크면 양수를 반환한다. qsort는 이 비교 함수를 사용하여 배열 arr의 원소를 정렬한다.