삽입 정렬 (Insertion Sort)

작성자 : 김문규
최초 작성일 : 2008.10.16

Pseudo Code

INSERTION-SORT(A, n) ⊳A[1 . . n]

    for j ←2 to n
        do key ←A[ j]
            i ← j – 1
            while i > 0 and A[i] > key
                do A[i+1] ←A[i]
                i ← i – 1
            A[i+1] = key

말로 약간 풀어보면
1. n개의 크기를 가지는 배열이 있다고 합시다.
2. j 값을 2부터 시작해서 하나씩 증가시킵니다.
3. A[j]의 위치에 있는 값을 A[j-1]의 위치에 있는 값과 비교합니다.
4. A[j] < A[j-1] 이면 서로의 값을 바꿉니다. 아니면 여기서 정렬이 종료됩니다.
5. 값을 바꾸었다면 다시 바꾼 위치가 A[j]가 되고 4번을 다시 수행합니다.

이해가 되시나요?  아래의 그림을 보시면 명확해 지실 겁니다.