정의
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입해 정렬을 완성하는 알고리즘
예시
삽입 정렬은 2번째 자료부터 시작하여 그 요소의 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬한다.
즉,
2번째 자료는 1번째 자료,
3번째 자료는 2, 1번째 자료,
4번째 자료는 3, 2, 1번째 자료와
비교한 후 해당 자료를 삽입할 위치를 찾는다.
자료가 삽입될 위치를 찾았다면 해당 위치에 자료를 삽입하기 위해 다른 자료들을 한칸 씩 뒤로 이동시킨다.
예제
Reference
땅콩의 모험 (server)