-
삽입 정렬
선택 정렬과 버블 정렬과 달리 1개짜리 배열로 시작하여 크기를 하나씩 늘려나가는 방식으로 정렬을 진행한다.
삽입 정렬 알고리즘
배열 A[1...n]에 대해 A[n] < A[i] 인 i를 찾아 A[n]과 A[i]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다.
이를 수도 코드로 나타내면 다음과 같다.
삽입 정렬 알고리즘
InsertionSort(A[], n) { for i ← 2 to n { A[1...i]의 적당한 자리에 A[n]을 삽입한다 } }