시간을 기록하다

by 기록자

삽입 정렬(Insertion Sort)

초보의 알고리즘 2008/07/21 12:11

삽입 정렬이란 정렬되어 있는 레코드에 새로운 레코드를 적절한 위치에 삽입하는 방법이다.
아래 그림을 보는것이 이해하기 쉬울 것이다.

삽입 정렬

위 그림에서 빨간색으로 표현된 레코드는 정렬이 되어있는 레코드들이고 파란색으로 표현된 레코드는 정렬해야할 레코드들이다. 그림에서 녹색으로 표현된 15라는 값을 가진 레코드를 정렬하기 위해 먼저 정렬되어 있는 데이터들과 비교해서 15가 들어갈 자리를

찾고 15보다 큰 데이터들(17, 35)은 한 칸씩 뒤로 밀리면서 15가 들어갈 자리를 확보하게 된다.
이와같은 방식으로 마지막 레코드까지 수행하면 정렬이 완료된다.
삽입 정렬에서는 정렬을 위한 비교(위 그림에서는 15가 들어갈 자리를 찾기 위한 비교)시에 이진 탐색이나 보간 탐색과 같은 방법으로 삽입할 위치를 찾는다면 좀 더 좋은 성능을 기대할 수 있다.

아래는 삽입정렬의 소스코드이다.

Sort_insertion.c