36. 삽입정렬

문제

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

입력설명

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

출력설명

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

입력예제

6
11 7 5 6 10 9

출력예제

5 6 7 9 10 11

---

#include <stdio.h>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
	int n, i, j, temp, number[101];
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		scanf("%d", &number[i]);
	}
	
	for(i=1; i<n; i++){
		temp = number[i];
		for(j=i-1; j>=0; j--){
			if(number[j] > temp){
				number[j+1] = number[j];
			} else{
				break;
			}
		}
		number[j+1] = temp;
	}
	
	for(i=0; i<n; i++){
		printf("%d ", number[i]);
	}
	
	return 0;
}

삽입정렬은 우선 i=1부터 시작합니다. 후에 j=i-1로 0번째 인덱스가 될때까지 빼는식으로 for문을 짭니다.
temp에 number[i]의 값으로 초기화하고 number[j]가 temp보다 크다면 number[j+1] = number[j]하고 그렇지 않다면 break로 코드를 멈춥니다. 후에 이때 j가 0이였다면 for문을 나오면서 -1이 됩니다. 그러므로 +1값에 temp값을 넣어주면 정렬이됩니다.