정렬

📌 거품 정렬(Bubble Sort)

인접한 두 요소를 비교하여 큰 값을 뒤로 보내는 방식으로 정렬하는 알고리즘

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

• 평균 시간 복잡도: O(n^2)
• 최소 시간 복잡도: O(n) (입력 데이터가 이미 정렬된 경우)
• 최악 시간 복잡도: O(n^2)

📌 선택 정렬(Selection Sort)

주어진 배열에서 최솟값을 찾아 맨 앞으로 보내는 방식으로 정렬하는 알고리즘

fun selectionSort(arr: IntArray) {
    for (i in arr.indices) {
        var minIdx = i
        for (j in i + 1 until arr.size) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j
            }
        }
        arr[i] = arr[minIdx].also { arr[minIdx] = arr[i] }
    }
}

• 평균 시간 복잡도: O(n^2)
• 최소 시간 복잡도: O(n^2)
• 최악 시간 복잡도: O(n^2)

📌 삽입 정렬(Insertion Sort)

배열의 두 번째 요소부터 시작하여 앞쪽의 정렬된 부분과 비교하며 적절한 위치에 삽입하는 방식으로 정렬하는 알고리즘

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

• 평균 시간 복잡도: O(n^2)
• 최소 시간 복잡도: O(n) (입력 데이터가 이미 정렬된 경우)
• 최악 시간 복잡도: O(n^2)

📌 퀵 정렬(Quick Sort)

pivot 값을 기준으로 배열을 분할하여 정렬하는 알고리즘

fun quickSort(arr: IntArray, left: Int, right: Int) {
    val part = partition(arr, left, right)
    if (left < part - 1) {
        quickSort(arr, left, part - 1)
    }
    if (part < right) {
        quickSort(arr, part, right)
    }
}

private fun partition(arr: IntArray, left: Int, right: Int): Int {
    val pivot = arr[(left + right) / 2]
    var i = left
    var j = right
    while (i <= j) { // 해당 부분 배열에 대해 반복
        while (arr[i] < pivot) { // 피벗보다 큰 left를 찾음
            i++
        }
        while (arr[j] > pivot) { // 피벗보다 작은 right를 찾음
            j--
        }
        if (i <= j) { // left가 right보다 왼쪽에 있으면 둘이 자리 바꿈
            arr[i] = arr[j].also { arr[j] = arr[i] }
            i++
            j--
        }
    }
    return i
}

• 평균 시간 복잡도: O(n log n)
• 최소 시간 복잡도: O(n log n)
• 최악 시간 복잡도: O(n^2) (입력 데이터가 이미 정렬되어 있거나 역순으로 정렬되어 있는 경우)

📌 병합 정렬(Merge Sort)

배열을 반으로 나누어 정렬한 뒤, 다시 병합하는 방식으로 정렬하는 알고리즘

fun mergeSort(arr: IntArray, left: Int, right: Int) {
    if (left < right) {
        val mid = (left + right) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)
    }
}

private fun merge(arr: IntArray, left: Int, mid: Int, right: Int) {
    val leftArr = arr.copyOfRange(left, mid + 1)
    val rightArr = arr.copyOfRange(mid + 1, right + 1)
    var i = 0
    var j = 0
    var k = left
    while (i < leftArr.size && j < rightArr.size) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++]
        } else {
            arr[k++] = rightArr[j++]
        }
    }
    while (i < leftArr.size) {
        arr[k++] = leftArr[i++]
    }
    while (j < rightArr.size) {
        arr[k++] = rightArr[j++]
    }
}

• 평균 시간 복잡도: O(n log n)
• 최소 시간 복잡도: O(n log n)
• 최악 시간 복잡도: O(n log n)

📌 힙 정렬(Heap Sort)

완전 이진 트리인 힙 자료구조를 이용하여 정렬하는 알고리즘

fun heapSort(arr: IntArray) {
    for (i in arr.size / 2 - 1 downTo 0) {
        heapify(arr, arr.size, i)
    }
    for (i in arr.size - 1 downTo 1) {
        arr[0] = arr[i].also { arr[i] = arr[0] }
        heapify(arr, i, 0)
    }
}

private fun heapify(arr: IntArray, n: Int, i: Int) {
    var largest = i
    val left = 2 * i + 1
    val right = 2 * i + 2
    if (left < n && arr[left] > arr[largest]) {
        largest = left
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right
    }
    if (largest != i) {
        arr[i] = arr[largest].also { arr[largest] = arr[i] }
        heapify(arr, n, largest)
    }
}

• 평균 시간 복잡도: O(n log n)
• 최소 시간 복잡도: O(n log n)
• 최악 시간 복잡도: O(n log n)