[정렬] 코틀린으로 만들어보는 삽입 정렬(Insert Sort)

삽입 정렬(Insert Sort)

 

  삽입 정렬(Insert Sort)는 정렬이 완료된 부분과 정렬이 필요한 부분으로 나누고 정렬이 완료된 부분으로 값을 삽입하는 알고리즘이다. 비교적 다른 정렬 알고리즘보다 구현이 간단한 편이지만, 정렬해야 하는 리스트 또는 컬렉션의 크기가 크면 성능 저하가 일어나는 정렬 알고리즘이다. 따라서 크키가 작은 데이터를 정렬할 때 사용하기에 좋다.

 

 

#목차

• 개발환경
• 이론
• 코딩

(각 목차를 클릭하면 해당 내용을 바로 볼 수 있습니다.)

 

 

개발 환경

언어 : 코틀린(Kotlin)

IDE : IntelliJ IDE

 

 

이론

  예제에서는 오름차순으로 정렬하기 위해 가장 앞의 수를 기준으로 값을 비교, 삽입한다. 정렬 되는 과정을 아래 그림으로 정리했다. 

 

  정렬 미완료 부분에서 순차적으로 정렬을 시도한다.

 

첫 순회에서는 정렬된 부분이 1개이기 때문에 50과 비교 후, 30을 정렬 완료 부분에 삽입한다.

 

  30은 50보다 작으므로 두 값의 자리를 교환한다. 이때 정렬 완료 부분이 그만큼 증가하게 된다. 만약 50보다 큰 수였다면 자리는 교환하지 않는다. 이제 정렬이 완료된 값은 2개로 증가했다. 그 다음으로 정렬될 40도 위와 같은 과정으로 정렬된다.

 

  인덱스가 2인 40은 정렬 완료 부분의 모든 수를 비교한다.

 

  50보다는 작고, 30보다는 크기 때문에 50과 자리를 교환한다. 그리고 정렬 완료 부분이 증가한다. 모든 수가 정렬될 때까지 위 과정을 반복한다.

 

반응형

 

코딩

fun main() {
    var nums = arrayListOf(49, 13, 32, 1, 28)
    ...

    //정렬 후
    println("---------------- 정렬 후")
    insertSort(nums)
    nums.forEach { print("${it} ")}
}

fun insertSort(nums: ArrayList<Int>) {
    var startIdx = 1
    var lastIdx = 0
    var temp = 0

    //정렬이 미완료 된 부분의 시작 인덱스인 1부터 시작
    for (i in startIdx until nums.size) {
        temp = nums[i]
        lastIdx = i

        while ((lastIdx > 0) && (nums[lastIdx-1] > temp)) {
            //자리를 하나씩 뒤로 미룬다.
            nums[lastIdx] = nums[lastIdx-1]
            lastIdx--
        }

        //빈 자리에 값을 삽입한다.
        nums[lastIdx] = temp
    }
}

 

결과

 

평균 소요 시간

  최악의 경우 정렬된 부분의 모든 수와 비교를 해야한다. 따라서 빅오 표기법으로 나타냈을 때 O(n2)가 된다.