[kotlin] 코틀린으로 정렬 알고리즘 구현하기

14 Dec 2023

kotlin

정렬 알고리즘은 데이터를 특정한 순서로 재정렬하는 알고리즘으로, 컴퓨터 과학에서 매우 중요한 주제입니다. 이번에는 코틀린으로 몇 가지 유명한 정렬 알고리즘을 구현해보겠습니다.

1. 버블 정렬

버블 정렬은 단순하고 직관적인 알고리즘으로, 인접한 두 원소를 비교하여 필요에 따라 서로 교환하는 방식으로 동작합니다.

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

2. 삽입 정렬

삽입 정렬은 각 원소를 적절한 위치에 삽입하여 정렬하는 알고리즘으로, 이미 정렬된 부분과 비교하여 삽입하는 방식으로 동작합니다.

fun insertionSort(arr: IntArray) {
    val n = arr.size
    for (i in 1 until n) {
        val key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
}

3. 퀵 정렬

퀵 정렬은 분할 정복 방법을 사용하여 배열을 정렬하는 알고리즘으로, 피벗을 기준으로 작은 원소와 큰 원소로 나누어 계속 재귀적으로 정렬하는 방식으로 동작합니다.

fun quickSort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        val pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low - 1
    for (j in low until high) {
        if (arr[j] < pivot) {
            i++
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
    val temp = arr[i + 1]
    arr[i + 1] = arr[high]
    arr[high] = temp
    return i + 1
}

이렇게 코틀린으로 버블 정렬, 삽입 정렬, 퀵 정렬을 구현해보았습니다. 각 정렬 알고리즘의 동작 방식을 이해하고, 실제로 구현해보면서 알고리즘에 대한 깊은 이해를 얻을 수 있을 것입니다.

목차

1. 버블 정렬

2. 삽입 정렬

3. 퀵 정렬