이번에는 반복 알고리즘 중에 삽입 정렬 알고리즘을 알아봅시다.
삽입 정렬 알고리즘은 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘입니다. 이를 위해 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환합니다.
삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리)
반복(i:=1; i<n ; i:= i+1)
반복(j=i; j>0 ; j:=j-1)
조건(compare (base [j-1], base [j]) < 0)
temp: = base [j-1]
base[j-1] = base [j]
base[j] = temp
아니면
루프 탈출
예:
정렬 전: 10 9 2 11 19
1.1회전: 9 10 2 11 19 (i:1,j:1, 0과 1 교환)
2.1회전: 9 2 10 11 19 (i:2,j:2, 1과 2 교환)
2.2회전: 2 9 10 11 19 (i:2,j:1, 0과 1 교환 )
3.1회전: 2 9 10 11 19 (i:3,j:3)
4.1회전: 2 9 10 11 19 (i:4,j:4)
삽입 정렬의 범위를 넓혀가면서 새롭게 범위에 포함하는 원소의 위치를 찾는 방법을 사용한다고 하였습니다. 따라서 내부 반복문을 수행하기 전의 선행 조건은 새롭게 범위에 포함하는 원소를 제외한 나머지 앞의 원소들은 정렬 상태라는 것입니다. 내부 반복문에서는 j를 새롭게 범위에 포함한 원소의 인덱스부터 출발합니다. 그리고 앞으로 이동하면서 자신보다 더 큰 값이면 자리를 교체하는 것을 반복합니다. 만약 자신보다 작거나 같은 값을 만나면 반복문을 탈출합니다. 물론 j가 0이면 더 이상 앞의 요소가 없으므로 반복문을 탈출합니다. 따라서 내부 반복문의 루프 변성은 j가 순차적으로 0으로 향한다는 것입니다. 그리고 루프 불변성은 인덱스 j에서 인덱스 i 사이에 있는 요소는 j번째의 요소보다 큰 값이라는 것입니다.
삽입 정렬의 외부 반복문의 루프 변성은 i가 점진적으로 n으로 증가한다는 성질입니다. 그리고 루프 불변성은 인덱스 0에서 i 사이의 요소는 정렬 상태를 유지한다는 것입니다. 따라서 루프 변성과 루프 불변성을 통해 위 알고리즘은 타당함을 증명할 수 있습니다.