[Kotlin] Sorting - 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

 

 

 

 아직 정렬되어 있지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다.

삽입 정렬을 반복할 때마다 하나의 입력 요소가 제거되고,  정렬된 list내에서 해당 요소가 속한 위치가 검색되어 삽입된다. ( 입력 요소가 없을 때까지 반복)

 

 

class InsertionSort: AbstractSortStrategy() {
    override fun <T : Comparable<T>> perform(arr: Array<T>) {
        for (i in 1 until arr.size) {
            for (j in i downTo 1) {
                if (arr[j - 1] < arr[j]) break
                arr.exch(j, j - 1)
            }
        }
    }
}

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

참고

https://github.com/bmaslakov/kotlin-algorithm-club/blob/master/src/main/io/uuddlrlrba/ktalgs/sorts/InsertionSort.kt

GitHub - bmaslakov/kotlin-algorithm-club: Algorithms and data structures in Kotlin.