삽입 정렬(Insertion Sort) - 알고리즘

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫번째 자료, 네 번째 자료는 세 번째, 두 번째 , 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 

그림으로 된 자세한 설명을 보시려면 아래 더보기를 클릭하세요.

배열에 8 5 6 2 4 가 저장되어 있다고 가정하고 자료를 정렬하면, 

1회전 : 두 번째 자료인 5를 key로 해서 그 이전의 자료들과 비교한다.

Key 값 5 와 첫 번째 자료인 8을 비교한다. 8이 5보다 크므로 8을 5자리에 넣고 key 값 5를 8의 자리인 첫 번째에 기억시킨다.

2회전 : 세 번째 자료인 6을 key 값으로 해서 그 이전의 자료들과 비교한다.

key 값 6과 두 번째 자료인 8을 비교한다. 8이 key 값보다 크므로 8을 6이 있던 세 번째 자리에 기억시킨다.

key 값 6과 첫 번째 자료인 5를 비교한다. 5가 key 값보다 작으므로 key 값 6을 두 번째 자리에 기억시킨다.

3회전 : 네 번째 자료인 2를 key로 해서 이전의 값들과 비교하여 교환.

4회전 : 다섯 번째 자료인 4를 key값으로 해서 이전의 자료들과 비교하여 교환한다.

삽입정렬의 결과로 2 4 5 6 8이 된다는 것을 알 수 있다.

이해가 잘되지 않는 부분이 있으시면 주저하지 말고 댓글을 달아주세요!!^^