[C] C언어에서 qsort 사용하기
C언어의 stdlib.h에서 제공하는 정렬함수인 qsort를 사용해보자
환경
- C언어 및 컴파일러
Quick Sort란?
원리
- pivot을 정하고 pivot보다 작은 값들을 pivot의 왼쪽 pivot보다 큰 값들은 pivot의 오른쪽으로 위치시키고 pivot의 왼쪽 값들과 오른쪽 값들을 각각 따로 또 재귀를 통해 분할정복한다.
특징
O(nlogn)의 성능을 보이는 정렬 알고리즘중에 하나로 최악에는O(n^2)의 성능을 보이지만 일반적으로 빠른 성능을 나타내기에 보편적으로 많이 쓰는 알고리즘 입니다.Divide and Conquer이라는 분할정복 방법으로 정렬을 진행하며 자세한 부분은 다음을 참고하시면 좋습니다.in-place sorting: 정렬 할 원소들을 위한 추가적인 메모리를 사용하지 않고 현재 메모리에서 정렬을 진행
C에서 Quick Sort인 qsort함수 사용하기
기본 구조
기본적으로 stdlib.h에서 Quick Sort 함수인 qsort 함수를 제공해주며 아래와 같습니다.
void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *);
- base: 정렬하고자 하는 배열의 포인터입니다.
- nel: 배열의 각 원소들의 총 수입니다.
- width: 배열에서 원소 하나의 크기입니다.
- (*compare): 비교를 수행할 함수 포인터입니다. C언어에서는 함수를 선언하고 구현한 후에 다음처럼 포인터로 특정 함수를 지정할 수 있습니다.
비교 함수에 대해서
4번째 인자에 대해서 조금 더 자세히 설명하면 비교함수 내부에는 1, 0 , -1중에 하나를 반환해야합니다. 만약 오름차순으로 정렬을 하고 싶다면 비교함수 내부에서 첫번째 변수가 두번쨰 변수보다 클 때 1을 첫번째 변수가 두번째 변수보다 작을 때 -1을 같을 때 0을 반환하도록 작성하면 됩니다. 물론 내림차순의 경우 1과 -1을 반환하는 부분의 등호를 바꾸어주면됩니다.
예제 코드
예제 코드는 아래와 같습니다.
HelloWorld.c
#include <stdio.h>
#include <stdlib.h>
// 오름차순으로 정렬할 때 사용하는 비교함수
int static compare (const void* first, const void* second)
{
if (*(int*)first > *(int*)second)
return 1;
else if (*(int*)first < *(int*)second)
return -1;
else
return 0;
}
int main()
{
int arr[] = {32, 11, 97, 42, 21, 70, 56, 67, 88, 100};
int array_size = sizeof(arr) / sizeof(int);
int i;
// 정렬 전
for (i = 0; i < array_size; i++) printf("%d ", arr[i]);
printf("\n");
qsort(arr, array_size, sizeof(int), compare);
// 정렬 후
for (i = 0; i < array_size; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}
결과는 아래와 같습니다.
