문제 번호 1421 --삽입 정렬(Insertion Sort)

1421: 삽입 정렬(Insertion Sort)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 144  해결 문제 수: 67
[제출][채점상황][게시판][:]

문제 설명

삽입 정렬(Insertion Sort)은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘입니다. 이 알고리즘은 뒤섞여 있는 카드를 순서대로 정리하는 방법과 같이, 카드를 한 장씩 뽑아 값에 따라 적절한 곳에 끼워 넣는 것을 반복하여 정리한는 것 처럼, 데이터 집합에서 요소를 하나식 뽑아 적절한 곳에 끼워 넣는 것을 반복하여 데이터 집합을 정렬하는 방법입니다.

입력데이터 : 6 4 2 3 1 5

1단계 : 4 6 2 3 1 5     -> 4를 1번째 자리에 삽입

2단계 : 2 4 6 3 1 5     -> 2를 1번째 자리에 삽입

3단계 : 2 3 4 6 1 5     -> 3을  2번째 자리에 삽입

4단계 : 1 2 3 4 6 5     -> 1을 1번째 자리에 삽입

5단계 : 1 2 3 4 5 6     -> 5를 5번째 자리에 삽입

위와 같이 정렬 과정을 거칠때, 정렬의 각 단계에서 정렬이 필요한 요소가 삽입될 자리를 출력하는 프로그램을 작성하시오.

입력

첫 줄에는 정렬하고자 하는 데이터의 갯수 n이 입력된다.( 2 <= n <= 100)

둘째 줄에는 n개의 데이터가 공백을 기준으로 입력된다.

출력

 정렬되는 각 단계별 데이터가 삽입되는 위치를 출력한다.

입력예시

6
6 4 2 3 1 5

출력예시

1
1
2
1
5

도움말

출처

 

[제출][채점상황]