Es la vida~

[삽입정렬 (Insertion Sort)]

왼쪽의 그림과 같이 삽입정렬 (Insertion Sort)은 이미 정렬 완료된 배열(그림 상의 회색)과 새로운 데이터(그림 상의 빨간색)를 비교 후 새로운 데이터를 순서에 맞게 삽입해가며 정렬하는 알고리즘이다.

그림의 각 절차에 따른 설명은 하기를 참고한다.

(a) 2번째 원소인 "7"과 기정렬 완료된 배열과 비교 : 변동 없음.

(b) 3번째 원소인 "2"와 기정렬 완료된 배열과 비교 : "2"가 1번째 원소로 이동하고 이후의 원소들은 Shift right

(c) 4번째 원소인 "5"와 기정렬 완료된 배열과 비교 : "5"가 3번째 원소로 이동하고 이후의 원소들은 Shift right

(d) 5번째 원소인 "1"과 기정렬 완료된 배열과 비교 : "1"이 1번째 원소로 이동하고 이후의 원소들은 Shift right

(e) 6번째 원소인 "4"와 기정렬 완료된 배열과 비교 : "4"가 4번째 원소로 이동하고 이후의 원소들은 Shift right

(f) 완성.

장점 : 구현이 간단하다.

단점 : 배열이 길어질수록 효율이 떨어진다. 알고리즘의 효율성은 O(N2)