삽입정렬(Insertion Sort)

1: for j = 1 to A.length

2:     key = A[j]

3:     //A[j]를 정렬된 배열 A[1...j-1]에 삽입한다.

4:     i=j-1

5:     while i>=0 그리고 A[j] > key

6:         A[i + 1] A[i]

7:         i= i-1

8:     A[i + 1] = key

 

(배열은 인덱스 0부터 시작하기 때문에 책에 나온 것을 약간 수정함)

A[j](=key)값을 기준으로

왼쪽(A[1...j-1]) 값은 정렬된 배열

오른쪽(A[j+1...n])값은 정렬되지 않는 배열이다.

 

1: 키값을 루프돌릴 반복문

 

2: j번째에 해당하는 키값 설정

 

4: j를기준으로 왼쪽의 정렬된 배열에 key값을 삽입하기 위해

j바로 옆인 j-1의 값을 i에 저장

 

5: i가 j-1부터 0까지 루프돌리기 위한 while

추가적으로 j-1 ~ 0 번째까지 중 key값보다 작으면

 

6: 해당 인덱스에 위치한 배열의 값을

키값의 위치(j-1이나 i+1은 key값이 위치한 같은 인덱스값)에 저장

 

7:j를 왼쪽으로 한칸 이동하기 위한 연산

 

8: while의 연산이 이루어지면 key값이 위에 연산된 인덱스 위치로 저장됨

while의 연산이 이루어지지않았으면 key값은 그대로 key위치에 저장됨

 

아래는 java로 코드화한 것.