삽입 정렬

정렬 문제를 해결하는 알고리즘 중 하나

 

정렬 문제

입력: n개 수들의 수열 <a₁,a₂,a₃...a_n>

출력: a₁ ≤ a₂ ≤ a₃ ≤ a₄ ≤ a_n... 을 만족하는 입력수열의 순열

 

정렬하고자 하는 숫자를 키라고 하며 입력으로는 n개의 원소 배열 A가 주어진다면 의사코드는 아래와 같다.

 

의사코드(Pseudo code)

 

Insertion-Sort(A)

Insertion-Sort(A)
for j=2 to A.length
    key = A[j]
    //A[j]를 정렬된 배열 A[1...j-1]에 삽입한다
    i=j-1
    while i > 0 and A[i] > key
    	A[i+1]=A[i]
        i = i - 1
    A[i+1] = key

 

알고리즘 타당성

 

초기조건

j=2 인 경우에서 시작하므로 해당 상태에서 루프의 불변성이 성립되는지를 확인해야한다.

부분 배열 A[1 ~ j-1] 이라는 부분 배열이 존재하는데 j=2이므로 해당 부분 배열은 A[1]과 같고 하나의 원소만이 있으므로 정렬되어있다. 따라서 초기 조건에서 루프의 불변성이 성립한다.

 

유지조건

루프가 반복되면서도 불변성이 성립하는지를 확인해야 한다.

 

j가 일씩 커지면서 j 보다 작은 위치에 있는 키들을 정렬한다.

즉, A[ j ]가 정렬된 위치를 찾을 때까지 A[j-1], A[j-2], A[j-3]... 을 한 칸 씩 이동하다 A[ j ] 를 적절한 위치에 삽입한다. 그렇게 된다면 A[1 ~ j]는 j가 증가한 이후에도 정렬된 상태를 유지하므로 루프의 불변성이 유지된다.

 

while 내부에서도 루프에 따라 불변성이 유지되야하는지를 확인해야하는데, A[1 ..  j]은 이미 정렬된 상태이며, 해당 상태에서 A[i + 1] = A[ i ]를 반복한다. 정렬된 상태에서 오른쪽으로 이동하는 것만을 반복하므로 정렬된 상태를 유지한다.

 

두 루프 모두에서 정렬된 상태를 유지하여 유지조건을 충족한다 할 수 있다.

 

종료 조건

종료되었을 때를 확인해야한다. 루프의 종료는 j가 A.length보다 커졌을 때 발생한다. j는 1씩 증가하므로 j=n+1이 되는 경우 종료된다는 것이다. 유지 조건에서 루프 불변성이 유지되므로 A[1 .. n]은 j가 n+1일 때 정렬되어있다. 이때 A[1 .. n]이 배열 전체에 해당하므로 배열 전체가 정렬된 이 알고리즘은 타당하다.