알고리즘 문제를 해결하다보면 문자열 정렬 문제를 풀어야 하는 경우가 있습니다.
테스트 케이스의 수가 얼마 안되는 문자열 정렬 문제는, 우리가 자주 사용하는 버블 정렬이나 선택 정렬을 통해 풀 수 있지만
테스트 케이스가 많아지면 시간 초과로 인해 문제를 해결하지 못하는 경우가 생기기도 합니다.
우리는 시간 초과를 해결하기 위해서 정렬 방식을 변경해야 하는데, 이번 글에서는 비교 정렬 방식 중 가장 빠른 퀵 정렬을 사용해보려고 합니다.
직접 퀵 정렬을 구현하려면 힘들지만, C언어에서는 qsort라는 함수를 제공하고 있어 편하게 사용할 수 있습니다.
qsort를 사용하기 전에 qsort 함수의 구조를 먼저 알아보겠습니다.
void qsort(
void *base,
size_t num,
size_t width,
int (__cdecl *compare )(const void *, const void *)
); qsort 함수를 위해서는 비교할 값들이 들어있는 배열 *base, 배열의 크기 num, 배열에 있는 요소의 크기 width, 그리고 비교 함수가 들어갑니다.
배열, 배열의 크기, 배열 요소의 크기는 우리가 알고 있는 부분이니 넘어가고 비교 함수에 대해서 알아보도록 하겠습니다.
비교 함수는 매개 변수로 받은 두 개의 값을 비교한 뒤, 값 중 하나를 리턴하는 함수입니다.
우리는 문자열을 비교해야 하니 문자열 a와 b를 받은 뒤 strcmp로 값을 비교한 결과값을 리턴하는 비교 함수를 구성해 보겠습니다.
int compare(const void *a, const void *b)
{
return strcmp(a, b);
}제가 작성한 비교 함수 입니다.
void * 형으로 a와 b를 받고, strcmp를 통해서 a와 b를 비교한 결과값을 리턴합니다.
만약 "a"와 "b"를 비교한다면 -1이 리턴 되겠네요.
이제 이렇게 구성한 비교 함수를 이용해서 qsort 함수를 사용해보도록 하겠습니다.
에서 확인하실 수 있습니다.
저는 문자열을 입력 받아 arr이라는 2차원 배열에 저장을 했고, 요소의 갯수는 n개 입니다.
qsort(arr, n, sizeof(arr[0]), compare);qsort 함수는 이런식으로 사용하시면 됩니다.
그 다음 실행해보시면 상당히 빠른 속도로 정렬되는 걸 보실 수 있습니다.