3. 삽입 정렬(Insertion Sort)

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

[1, 2, 5, 4, 3] -> 첫 번째는 그대로 둡니다.

[1, 2, 4, 3, 5] -> 두 번째도 오름차순으로 있어 그대로 둡니다.

[1, 2, 5, 4, 3] -> 세 번째도 앞의 숫자보다 크기 때문에 그대로 둡니다.

[1, 2, 5, 4, 3] -> 네 번째는 앞의 숫자 5보다 작기 때문에 앞으로 이동합니다.

[1, 2, 4, 5, 3] -> 다섯 번째는 앞의 숫자 보다 작기 때문에 4 앞으로 이동합니다.

[1, 2, 3, 4, 5]

 

삽입 정렬은 작은 수에서만 효과적인 경우가 많습니다. 또한 이미 정렬되어 있는 배열에 새로운 원소를 집어 넣어 다시 정렬할 때 효과적입니다. 버블 정렬, 선택 정렬보다 빠름