[C] 백준 2750번 수 정렬하기

링크
https://www.acmicpc.net/problem/2750

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5
5
2
3
4
1

예제 출력 1

1
2
3
4
5

아이디어 스케치

• 이 문제는 단순히 for문과 조건문을 이용하는 버블 정렬을 이용해도 시간 초과가 발생하지 않는다.
• 하지만 조금 고급지게 풀기 위해 c언어 stdlib 헤더파일에 있는 qsort(퀵정렬)을 이용 하면 될 것이다.

코드 분할 설명

for (int i = 0; i < N; i++)
	scanf("%d", &arr[i]);

qsort(arr, N, sizeof(int), compare);		//퀵 정렬

• N만큼의 숫자를 입력 받아 배열에 저장한 후 퀵 정렬을 수행하는 코드이다.
• 퀵정렬의 인자로는 ([정렬 할 배열],[배열 요소의 갯수],[배열 요소의 개별 크기],[비교함수])이다.
• 만약 char형이면 sizeof(char)을 입력하면 된다.

int compare(const void* first, const void* second)
{
	int a = *(const int*)first;
	int b = *(const int*)second;

	if (a > b)
		return 1;			//오름 차순 정렬
	else if (a < b)
		return -1;
	else
		return 0;
}

• 퀵 정렬에서 사용하는 비교 함수이다.
• 함수 전달 인자로는 const void* 형으로 받는다.
• 배열의 변수형은 int형이므로 (const int)형으로 전달 인자를 형변환 한다.
• return이 1인 경우에 swap을 하고, 우리는 오름차순으로 정렬 해야 하므로 first>second 일 때 return 1을 해줌으로써 오름차순 정렬을 한다.

전체 코드

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

int compare(const void* first, const void* second)
{
	int a = *(const int*)first;
	int b = *(const int*)second;

	if (a > b)
		return 1;			//오름 차순 정렬
	else if (a < b)
		return -1;
	else
		return 0;
}

int main()
{
	int arr[1001];
	int N;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	qsort(arr, N, sizeof(int), compare);		//퀵 정렬

	for (int i = 0; i < N; i++)
		printf("%d\n", arr[i]);

	return 0;
}

제출 결과

아래는 버블 정렬을 이용하였고 위에는 퀵 정렬을 이용하였다.