[C] 백준 2750 수 정렬하기

문제

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

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

학습

여러가지 정렬을 적용할 수 있지만, 나는 그 중에서도 버블정렬을 사용하였다. 버블정렬은 서로 인접한 숫자끼리 비교한 후 num[i-1]이 num[i]보다 크면 서로 교환하는 정렬이다. 버블정렬을 잘 이해하고 있으면 tmp변수를 하나 만들어  num[i],num[i-1]을 서로 교환하는 코드를 작성하는 것은 떠올릴 수 있을 것이다. 한 번의 버블이 끝나면 flag의 값을 1씩 증가시키고, 입력받은 N-1과 같아지면 break문을 통해서 while문을 빠져나오게 구현하였다.

버블정렬은 한 번의 정렬이 끝나고 그 만큼을 다시 반복하며 정렬하는 것이므로 O(n^2)의 시간 복잡도를 갖는다. 

코드

#define CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int num[1024]={0, };
	int N, tmp=0, flag = 0;

	scanf("%d",&N);

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

	while(1){
	flag = 0;
	for(int i=1; i<N; i++){
		if (num[i-1]>num[i]){
			tmp=num[i];
			num[i]=num[i-1];
			num[i-1]=tmp;
	}
	else
		flag++;
	}
	if (flag == N-1)
		break;
	}
	for (int i=0; i<N; i++){
		printf("%d\n", num[i]);
	}
	return 0;
}

출처

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

2750번: 수 정렬하기