삽입정렬(Insertion Sort)

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

예제

아래의 그림은 5개의 데이터를 가진 배열을 삽입정렬을 이용하여 정렬을 완성하는 예제이다.

장점

데이터 갯수가 많지 않거나 어느 정도 정렬되어 있는 데이터의 경우 효율적

단점

정렬 대상 데이터가 자리를 찾아 들어갈 때까지 앞서 정렬된 데이터가 이동해야 하기 때문에
데이터의 갯수가 많아지면 비효율적이다.

References

• 위키백과 - 삽입정렬
• Do it! 자료구조와 함께 배우는 알고리즘 입문(한빛미디어)
• https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html