7225 : 삽입 정렬 구현
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
삽입 정렬(Insertion Sort)은 두 번째 원소부터 시작하여 앞쪽 정렬된 부분의 적절한 위치에 삽입해나가는 정렬 알고리즘입니다.
삽입 정렬을 직접 구현하여 각 삽입 단계를 마친 후의 전체 배열 상태를 출력하십시오.
시간 복잡도는 최선 $O(N)$, 최악 $O(N^2)$입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
삽입 정렬을 직접 구현하여 각 삽입 단계를 마친 후의 전체 배열 상태를 출력하십시오.
시간 복잡도는 최선 $O(N)$, 최악 $O(N^2)$입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소의 개수 $N$이 주어집니다. ($1 \le N \le 500$)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
두 번째 원소부터 마지막 원소까지 각 삽입 단계를 마친 후의 전체 배열 상태를 줄바꿈으로 출력합니다.
총 $N-1$줄이 출력됩니다.
총 $N-1$줄이 출력됩니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
5 4 3 2 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5 3 2 1
3 4 5 2 1
2 3 4 5 1
1 2 3 4 5도움
각 단계 $i$에서
key = arr[i]를 저장한 후, arr[j] > key인 동안 원소를 뒤로 밀고 적절한 위치에 key를 삽입합니다. 삽입 후 배열 상태를 출력합니다.