• 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함.
• 배열이 길어질수록 효율이 떨어지지만, 구현이 간단함.
• 배열 자료구조를 사용함.

알고리즘

• 정렬은 2번째 원소부터 시작하여, 왼쪽의 원소들과 비교 후 삽입할 위치를 지정한 함.
• 그 이후 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입함.

예시


정렬되지 않은 배열로 가정하고, 오름차순으로 정렬 프로세스로 가정. → [5, 2, 4, 6, 1, 3]

1. 두 번째 원소부터 시작함. 5와 2를 비교하여 정렬하는 위치를 결정함.
   1. before : [5, 2, 4, 6, 1, 3]
   2. after : [2, 5, 4, 6, 1, 3]
2. 정렬된 배열 기반으로 값의 크기를 비교하여 다시 재정렬 수행.
   1. before sorted : [2, 5]
   2. element : 4
   3. after sotred : [2, 4, 5, 6, 1, 3]
3. 위 과정을 반복하여 정렬을 수행.

소스코드 - Kotlin

fun insertSort(intArray: IntArray) {
    for(i in 1 until intArray.size) {
        val temp = intArray[i]
        var aux = i - 1

        while((aux >= 0) && (intArray[aux] > temp)) { // 정렬된 부분과 비교
            intArray[aux+1] = intArray[aux]
            aux--
        }
        intArray[aux+1] = temp
    }
}

범위 및 함수 사용시 유의사항

• indices : IntRange타입을 반환하며**,** 수신객체의 전체 범위 반환. 위 예제 에선 0..6
• until : 범위의 마지막 요소를 포함하지 않음.
  • 0..5 => 0, 1, 2, 3, 4, 5
  • 0 until 5 => 0, 1, 2, 3, 4
• numbers.size , numbers.lastIndex 을 주의해서 사용.

장점

• 선택 정렬이나, 버블 정렬과 같은 알고리즘에 비하여 빠름.