백준 2750 (수 정렬하기)

수 정렬하기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

108598

61833

42631

58.328%

문제

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

입력

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

출력

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

예제 입력 1 복사

5
5
2
3
4
1

예제 출력 1 복사

1
2
3
4
5

 

<코드 1>

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 1000
int main(void)
{
	int N, temp;
	scanf("%d", &N);
	int arr[MAX];

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < N; i++)
		for(int j=0; j<N-1; j++)
			if (arr[j + 1] < arr[j])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		for (int i = 0; i < N; i++)
			printf("%d\n", arr[i]);
	return 0;
}

 

코드<2>

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 1000
void swap(int* a, int* b);
int main(void)
{
	int N;
	scanf("%d", &N);
	int arr[MAX] = { 0 };
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < N; i++)
	{
		int j = i;
		for (int k = i+1; k < N; k++)
		{
			if (arr[k] < arr[j])
				j = k;
		}
		swap(&arr[i], &arr[j]);
	}
	for (int i = 0; i < N; i++)
	{
		printf("%d\n", arr[i]);
	}
	return 0;
}
void swap(int* a, int* b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

 

<풀이>

  코드1은 버블정렬(서로 인접한 두 원소를 검사하여 정렬하는 알고리즘을 이용한 방법이다. 

  버블정렬을 통해 배열에 저장 된 7, 4, 5, 1, 3을 오름차순으로 정렬하는 방법은 다음 그림과 같다.

  코드2는 선택정렬을 이용한 방법이다. 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중    가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

선택정렬을 통해 배열에 저장 된 9, 6, 7, 3, 5를 오름차순으로 정렬하는 방법은 다음 그림과 같다.