Time Limit: 1s
Memory Limit: 128MB
삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.
각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다.
배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.
Insertion sort로 배열을 오름차순으로 정렬한 결과와 교환 횟수를 구해보자.
k번째 요소의 자리를 찾는 것은 더 빠른 방법이 있을 수도 있겠지만 이 문제에서는 뒤에서부터 앞으로 한 칸씩 이동하면서 앞의 요소와 비교하는 방식으로 한다.
* Line 1 : 정렬할 배열 갯수 N (1≤N≤1000)
* Line 2~N+1 : 배열 arr의 크기 n이 입력되고 그 뒤로 배열 arr의 원소들이 공백으로 구분되어 입력된다. (1 ≤ n ≤ 100, -2000 ≤ arr[i] ≤ 2000)
* Line 1~N : 정렬 중의 교환 횟수와 정렬 결과가 공백으로 구분되여 한 줄로 출력한다.
3 3 0 2 1 4 4 3 2 1 7 1 5 3 3 2 6 4
1 0 1 2 6 1 2 3 4 7 1 2 3 3 4 5 6
{3, 4, 1, 2}를 Insertion Sort로 정렬하기
2번째 요소(4) 검사하기:
3<4이므로 교환안함
3번째 요소(1) 검사하기:
4>1이므로 교환(1회) -> {3, 1, 4, 2}
3>1이므로 교환(2회) -> {1, 3, 4, 2}
4번째 요소(2) 검사하기:
4>2이므로 교환(3회) -> {1, 3, 2, 4}
3>2이므로 교환(4회) -> {1, 2, 3, 4}
1<2이므로 교환안함
{3, 4, 1, 2}를 Insertion Sort로 정렬할 때 교환은 총 4번 발생한다.