백준 알고리즘 #1 - qsort

이번 포스트에서는 qsort에 대해 알아보겠습니다.

qsort, 즉 퀵 정렬은 C언어에서 제공하는 '정렬' 라이브러리 함수입니다.
백준을 풀다 보면 여러 가지 알고리즘이 필요하지만, 정렬을 해야만 취할 수 있는 알고리즘이 다수 있습니다.

그러기에 qsort는 선택이 아닌 필수적으로 알아둬야하는 함수입니다.

 

 

 

🏳️ qsort를 사용하기 위해 필요한 헤더 파일?
 - qsort는 <stdlib.h>헤더 파일을 불러서 사용할 수 있습니다.

 

 

 

🏳️ qsort의 인자는?
 - qsort는 4개의 인자를 가집니다. 아래의 형식을 따라서 사용합니다.

#include <stdlib.h>

qsort(정렬할 배열의 주소, 배열 요소 갯수, 배열 요소 크기, 사용할 함수);

ex)
qsort(ary,num,sizeof(char),compare;

 

 

 

 

🏳️ qsort의 기준 함수 작성법?

- 기준 함수는 int 형을 반환하는 형식입니다. 

  아래 코드로 qsort를 실행하게 되면 오름차순이 됩니다.

  즉 ary [6]이 {1, 3, 4, 5, 8, 9}로 정렬이 되는거죠. 

  return 1(양수)일 경우에는 True값이 반환되어 정렬을 수행하고,

  return -1(음수)일 경우에는 False값이 반환되어 정렬을 수행하지 않습니다.

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

int compare(const void* num1, const void* num2)
{
	int a = *(int*)num1;
	int b = *(int*)num2;
	if (a > b)
	{
		return 1;
	}
	else if (a < b)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	int ary[6] = { 3, 4, 1, 9, 5, 8 };
	qsort(ary, 6, sizeof(int), compare);
}

 

 

 

 

🏳️ 꼭 배열이 int형이여야 qsort가 사용가능 하나요?

 - 꼭 그렇지 않습니다. char, float, double, 구조체 타입도 비교가 가능합니다.

 

 <char형식 일때>

 아래형식으로 정렬을 시키면 아스키코드 순서(사전 순서)로 정렬이 됩니다.

 ary [6] = { 'a', 'b', 'c', 'e', 'f'}

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

int compare(const void* num1, const void* num2)
{
	char a = *(char*)num1;
	char b = *(char*)num2;
	if (a > b)
	{
		return 1;
	}
	else if (a < b)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	char ary[6] = { 'e', 'f', 'b', 'c', 'a'};
	qsort(ary, 6, sizeof(char), compare);
	for (int i = 0; i < 6; i++)
	{
		printf("%c ", ary[i]);
	}
}

 

 <구조체 형식 일 때>

 구조체의 형식을 적어주면서 문자열이면 strcmp 함수를, int나 double의 정렬을 원하면 위와 같이 해주시면  됩니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct memo
{
	int count;
	char str[100];
}memo;

int intcompare(const void* num1, const void* num2)
{
	memo * a = (memo*)num1;
	memo * b = (memo*)num2;
	if ((a->count) > (b->count))
	{
		return 1;
	}
	else if ((a->count) < (b->count))
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int stringcompare(const void* num1, const void* num2)
{
	memo * a = (memo*)num1;
	memo * b = (memo*)num2;
	return strcmp(a->str, b->str);
}

int main(void)
{
	int num = 0;
	scanf("%d", &num);
	memo* ary = (memo*)malloc(sizeof(memo) * num);
	for (int i = 0; i < num; i++)
	{
		scanf("%d %s",&ary[i].count, ary[i].str);
	}
	qsort(ary, num, sizeof(memo), intcompare);
	qsort(ary, num, sizeof(memo), stringcompare);
    free(ary);
}

 

 

 

여기서 주의 깊게 봐야 할 점은 intcompare 후에 stringcompare함수로 qsort가 이루어진다는 점입니다.

첫 번째의 qsort(ary, num, sizeof(memo), intcompare);로 정렬을 하게 되면 구조체 배열이 구조체에 입력된 숫자 순으로 정렬이 됩니다.

두 번째의 qsort(ary, num, sizeof(memo), stringcompare);로 정렬을 하게 되면 구조체 배열이 구조체에 입 련된 문자열의 사전순으로 정렬이 됩니다.

즉, 우선순위를 고려해서 정렬을 해야 할 때 잘 고려해야 된다는 걸 알 수 있습니다.