삽입 정렬

삽입 정렬은 수를 정렬된 상태로 삽입함으로서 정렬하는 방법이다.

A라는 배열이 있을 때

{A[1]}을 초기에 정렬된 배열이라고 하고 이 배열의 처음부터 끝까지를 확인하면서 A[i]보다 큰 수가 나오면 그 자리에 A[i]를 삽입한다. 이때 원래 자리에 있던 수를 비롯한 A[i]보다 큰 수들은 한 칸씩 뒤로 밀리게 된다. 또한 이 정렬된 배열을 따로 만들지는 않으며, A의 앞부분에 나타낸다.

 

INSERTION-SORT(A)
	for j=2 to A.length
    	key=A[j]
        i=j-1
        while i>0 and A[i]>key
        	A[i+1]=A[i]
            i=i-1
        A[i+1]=key

위는 배열 A에 대한 삽입 정렬의 의사코드이다.

A.length는 수의 개수이고 key는 현재 정렬해야하는 수를 의미한다.

 

삽입정렬에 대한 이해를 완료했다면 아래 문제를 해결해 보기를 바란다.

 

 

N개의 양의 정수 A[1], A[2], A[3], ..., A[N] 이 주어진다.

이를 오름차순 정렬하여 출력하는 프로그램을 작성하시오.

 

입력 조건

2 ≤ N ≤ 1000, A[i] ≤ 2^31-1

모든 정수는 하나의 공백을 사이에 두고 입력된다.

 

출력 조건

N개의 정수를 오름차순으로 정렬하여 출력하라.

모든 정수는 하나의 공백을 사이에 두고 출력한다.

 

input

5

5 2 4 6 1

 

output

1 2 4 6 1

 

선택정렬 입출력 데이터.zip

0.01MB