[정렬] 코틀린으로 만들어보는 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

 

  선택 정렬(Selection Sort)은 수열 중 하나의 숫자를 선택한다.(여기서는 오름차순으로 정렬할 것이기에 가장 작은 수가 된다.) 그리고 위치해야할 자리로 자리를 교환한다. 이 과정을 모든 수가 정렬될 때까지 반복하는 알고리즘이다. 

  시간 복잡도 순으로 본다면, 선택, 버블 정렬과 같이 O(n2)가 소요된다. 하지만 버블 정렬보다 선택 정렬이 항상 더 우수하며 메모리가 제한된 경우에서는 성능상의 이점이 있다고 한다.

 

#목차

• 개발환경
• 이론
• 코딩

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

 

 

개발 환경

언어 : 코틀린(Kotlin)

IDE : IntelliJ IDE

 

 

이론

  수열  [30, 20, 10, 40, 50]을 선택 정렬을 이용해서 오름차순으로 정렬할 것이다. 

  변환되는 과정을 아래 그림으로 보자.

 

  수열 전체 범위에서 가장 작은 수를 찾는다.

 

  그리고 가장 왼쪽, 0번째 숫자와 자리를 바꾼다.

 

  1회 순회에서 찾은 가장 작은 수는 가장 앞으로 이동하며 정렬을 완료했다.

  하지만, 1회 순회로는 감이 잘 안올 수 있다. 2회 순회까지 살펴보자.

  먼저 가장 작은 수를 찾는다.

 

  그리고 역시 가장 왼쪽, 이제 1번째 숫자와 자리를 바꾼다.

 

  그럼 다음과 같이 두 번째 작은 수까지 정렬되고 다음 작은 수를 정렬 하기 위해 범위가 1 줄어든다.

 

이렇게 위의 과정을 총 5회 진행하면 수열이 오름차순으로 정렬된다.

이제 직접 코틀린으로 선택 정렬(Selection Sort)를 만들어 보자.

 

반응형

 

코딩

fun main() {
    val arrNums = arrayListOf(30, 20, 10, 40, 50)
    
    ...

    val selectionSort = SelectionSort(arrNums)
    val sortedArr = selectionSort.sort()

    print("\n정렬 후 : ")
    sortedArr.forEach {
        print("${it} ")
    }
}

//선택 정렬을 수행하는 클래스
private class SelectionSort(var arrNums: ArrayList<Int>) {
    fun sort() : List<Int> {
        var min:Int

        //작은 수를 먼저 찾는다.
        //<List>.indices 는 배열의 인덱스를 가져온다.
        for (i in arrNums.indices) {
            min = i
            for (j in i+1 until arrNums.size) {
                if (arrNums[j] < arrNums[min]) {
                    min = j
                }
            }

            //가장 앞자리 인덱스와, 가장 작은 수의 인덱스를 전달해, 두 값의 위치를 바꾼다.
            changePosition(arrNums, min, i)
        }

        return arrNums
    }

    //찾은 수와 자리를 바꾼다.
    private fun changePosition(nums: ArrayList<Int>, min: Int, i: Int) {
        var temp:Int
        temp = nums[min]
        nums[min] = nums[i]
        nums[i] = temp
    }
}

 

결과

 

평균 소요 시간

  정렬이 되는 시간은 자리를 바꾸는데는 2개의 값만 바꾸면 되기 때문에 시간이 걸리지 않는다. 하지만 가장 작은 수를 찾기 위해 수열 전체를 탐색하기 때문에 위 예제 같은 경우, 총 5개의 숫자이므로 5 x 5 x 5 x 5 x 5 로 5²이다.

  빅오 표기법으로 나타내면 O(n²)가 된다.