퀵 정렬
퀵 정렬 소개
퀵 정렬(Quick Sort) 알고리즘은 분할 정복(Divide and Conquer) 방법을 이용한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 다음과 같은 순서로 작동합니다. 퀵 정렬 알고리즘을 구현하는 내용은 이 강의의 내용을 벗어나기에 가볍게 읽고 넘어가세요.
- 먼저, 배열에서 하나의 원소를 선택합니다. 이 원소를 '피벗(pivot)'이라 합니다.
- 피벗을 기준으로 배열을 두 부분으로 나눕니다. 하나는 피벗보다 작거나 같은 원소들로 구성되고, 다른 하나는 피벗보다 큰 원소들로 구성됩니다. 이 과정을 '분할(Partition)'이라고 합니다.
- 분할된 두 부분에 대해 재귀적으로 같은 과정을 반복하여 정렬을 수행합니다.
퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 이는 대부분의 경우에서 효율적인 정렬을 보장합니다. 그러나 최악의 경우(이미 정렬된 배열 등) O(n^2)의 시간 복잡도를 가질 수 있습니다.
퀵 정렬 함수(qsort) 사용하기
C 언어는 다양한 알고리즘을 효과적으로 구현할 수 있는 다양한 라이브러리를 제공합니다. 이 중 퀵 정렬 알고리즘을 구현한 함수인 qsort는 배열의 원소 타입에 상관없이 어떤 타입의 배열도 정렬할 수 있습니다. 이는 qsort 함수가 비교 함수를 인자로 받아, 배열의 두 원소를 어떻게 비교할지 결정하기 때문입니다.
qsort는 "quick sort"의 줄임말로, 이름에서 알 수 있듯이 퀵 정렬 알고리즘을 구현한 함수입니다. 이 함수는 배열의 원소를 비교하는 사용자 정의 함수를 받아 이를 기반으로 배열을 정렬합니다. 이 비교 함수는 qsort()에 의해 호출되며, 두 원소를 비교하여 첫 번째 원소가 두 번째 원소보다 작으면 음수, 같으면 0, 크면 양수를 반환해야 합니다.
qsort() 함수의 원형은 다음과 같습니다:
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
여기서 각 매개변수는 다음과 같은 의미를 가집니다:
base: 정렬할 배열의 시작 주소를 가리킵니다.nitems: 배열의 원소 개수입니다.size: 각 원소의 크기입니다. 일반적으로sizeof연산자를 사용하여 이 값을 구합니다.compar: 비교 함수의 포인터입니다. 이 함수는 두 원소를 비교하여 첫 번째 원소가 작으면 음수, 같으면 0, 크면 양수를 반환합니다.
따라서, 사용자가 원하는 비교 함수를 작성하면 qsort()를 사용하여 다양한 조건으로 배열을 정렬할 수 있습니다.
아래에 주어진 코드는 compare라는 비교 함수를 정의하고, 이 함수를 qsort에 인자로 전달하여 배열을 정렬하는 예입니다. 비교 함수는 두 포인터를 인자로 받아, 첫 번째 인자가 두 번째 인자보다 작으면 음수, 같으면 0, 크면 양수를 반환합니다. 이 예제에서는 간단하게 두 정수의 차를 반환하도록 했습니다.
코드: qsort_example.c
#include <stdio.h>
#include <stdlib.h>
/**
* @brief 비교 함수
*
* 이 함수는 두 정수를 비교하여 첫 번째 정수가 작으면 음수, 같으면 0, 크면 양수를 반환합니다.
* 이 함수는 qsort 함수에 의해 호출되어 배열의 정렬 순서를 결정합니다.
*
* @param a 비교할 첫 번째 정수의 포인터
* @param b 비교할 두 번째 정수의 포인터
* @return 첫 번째 인자와 두 번째 인자의 차이값
*/
int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
/**
* @brief 프로그램의 메인 함수
*
* 이 함수에서는 정수 배열을 선언하고 qsort 함수를 호출하여 배열을 정렬합니다.
* 그 후, 정렬된 배열을 출력합니다.
*
* @return 프로그램의 종료 상태. 정상 종료 시 0을 반환합니다.
*/
int main(void)
{
// 정렬할 정수 배열
int numbers[] = { 3, 2, 1, 5, 4 };
int size = sizeof(numbers) / sizeof(numbers[0]);
// qsort 함수를 사용하여 배열 정렬
qsort(numbers, size, sizeof(int), compare);
// 정렬된 배열 출력
printf("정렬 후 배열: ");
for (int i = 0; i < size; i++)
{
printf("%d ", numbers[i]);
}
printf("\n");
return 0;
}
정렬 후 배열: 1 2 3 4 5
위 코드를 실행하면 오름차순으로 정렬된 결과를 얻을 수 있습니다. 입력 배열이 qsort 함수를 통해 오름차순으로 정렬되었음을 확인할 수 있습니다.
C 언어의 표준 라이브러리 함수인 qsort는 사용자가 원하는 비교 함수를 정의함으로써 다양한 정렬 조건을 적용할 수 있어 매우 유용한 도구입니다. 이를 통해 복잡한 정렬 알고리즘을 직접 구현하지 않고도 배열을 효과적으로 정렬할 수 있습니다.
참고로, compare 함수에서 void* 인자를 int*로 변환하는 이유는 qsort 함수가 모든 타입의 배열을 처리할 수 있도록 설계되었기 때문입니다. qsort 함수는 일반성을 유지하기 위해 void* 타입의 포인터를 사용합니다. void*는 "모든 타입의 포인터를 가리킬 수 있는" 범용 포인터입니다. 따라서 qsort 함수를 호출할 때 사용되는 비교 함수에서는 이 void* 포인터를 실제 데이터 타입(이 경우 int)의 포인터로 형 변환해주어야 합니다. 이렇게 함으로써 qsort는 어떤 타입의 배열이든 정렬할 수 있게 됩니다. 다시 말해, 이 비교 함수는 범용적인 qsort 함수가 특정 타입의 데이터를 처리할 수 있도록 "번역"해주는 역할을 하는 것입니다.