[개념] 삽입정렬 / c / 제한시간 없음

▣ 문제

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 삽입정렬입니다.

 

▣ 입력설명

- 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

▣ 출력설명

- 오름차순으로 정렬된 수열을 출력합니다.

 

▣ 입력 예시

6 11 7 5 6 10 9

 

▣ 출력 예시

5 6 7 9 10 11

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n, i, j;
	int num[100];
	int temp;

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

	for (i = 1; i < n; i++) {
		temp = num[i];
		for (j = i - 1; j >= 0; j--) {
			if (num[j] > temp)
				num[j + 1] = num[j];
			else break;
		}
		num[j + 1] = temp;
	}

	for (i = 0; i < n; i++) {
		printf("%d ", num[i]);
	}
	


	return 0;
}

 

삽입 정렬이 선택, 버블, 삽입 정렬중에서 가장 문제에서 출제 빈도가 높다.

 

삽입 정렬은 i번째의 수를 temp에 저장시키고 뒤에서 앞으로 숫자를 비교해가면서 정렬하는 방법이다.

 

삽입 정렬의 경우 평균적인 시간 복잡도는 O(N^2)이지만 최적의 경우에는 O(N)이다.