08/26 CS공부 - 알고리즘(퀵 정렬, 병합 정렬, 힙 정렬)

1. 퀵 정렬(Quick Sort)

피벗을 선택하여 피벗 왼쪽은 피벗보다 작은값, 오른쪽은 피벗보다 큰 값으로 분할(Partitioning) -> 피벗 좌우에 모인 원소들에 대해 반복, 피벗 선택과 Partitioning 방법에 따라 정렬 속도가 좌우됨

퀵 정렬의 경우 먼 거리의 원소끼리 비교하므로 속도를 높일 수 있음

작은 것으로 나누어 다시 합치는 분할 정복 알고리즘을 사용함

시간 복잡도

최악의 경우(피벗이 최소 또는 최대값인 경우) O(n^2), 평균적으로 O(nlogn)

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n)

장점

한 배열 안에서 교환을 수행하므로 메모리공간이 적게 필요하다.(제자리 정렬)
많은 경우에서 다른 O(nlogn) 알고리즘(병합 정렬)보다 빠르다.

단점

불안정정렬(Unstable Sort)이다.
최악의 경우 시간복잡도가 O(n^2)으로 크다.

코틀린 코드

class QuickSort {
    fun quickSort(arr: Array<Int>, low: Int, high: Int) {
        if (low < high) {
            val pi = partition(arr, low, high)

            quickSort(arr, low, pi - 1) // 피벗 기준 왼쪽 부분 정렬
            quickSort(arr, pi + 1, high) // 피벗 기준 오른쪽 부분 정렬
        }
    }

    private fun partition(arr: Array<Int>, low: Int, high: Int): Int {
        val pivot = arr[high] // 마지막 요소를 피벗으로 선택
        var i = low - 1 // 작은 요소의 인덱스

        for (j in low until high) {
            if (arr[j] <= pivot) {
                i++
                arr.swap(i, j)
            }
        }

        arr.swap(i + 1, high)
        return i + 1
    }

    private fun Array<Int>.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

2. 병합 정렬(Merge Sort, 합병 정렬)

주어진 배열을 반으로 나누어 다시 합치면서 정렬함, 배열 크기가 1이 될때까지 나누며 크기가 1이되면 정렬된 것으로 간주

분할 정복 알고리즘을 사용

시간 복잡도

시간 복잡도는 반드시 O(nlogn)을 보임(계속 반으로 분할하므로)

공간 복잡도

병합할 배열이 필요하므로 2n개의 공간이 필요하다 따라서 O(n)

장점

순차접근에 효율적인 LinkedList에 사용하면 좋음(LinkedList는 퀵정렬에서 사용하는 임의접근에서 불리)
시간 복잡도는 반드시 O(nlogn)을 보인다.
안정정렬(Stable Sort)이다.

단점

추가적인 배열이 필요해 공간복잡도가 크다
속도가 퀵정렬보다 느릴 수 있다.

코틀린 코드

class MergeSort {
    fun mergeSort(arr: Array<Int>): Array<Int> {
        // 배열의 크기가 1 이하라면 이미 정렬된 상태이므로 그대로 반환
        if (arr.size <= 1) {
            return arr
        }

        // 배열을 반으로 나눔
        val middle = arr.size / 2
        val left = arr.sliceArray(0 until middle)
        val right = arr.sliceArray(middle until arr.size)

        // 재귀적으로 두 부분을 정렬
        return merge(mergeSort(left), mergeSort(right))
    }

    private fun merge(left: Array<Int>, right: Array<Int>): Array<Int> {
        var i = 0
        var j = 0
        val result = mutableListOf<Int>()

        // 두 배열을 비교하여 작은 값을 결과 리스트에 추가
        while (i < left.size && j < right.size) {
            if (left[i] <= right[j]) {
                result.add(left[i])
                i++
            } else {
                result.add(right[j])
                j++
            }
        }

        // 남은 요소들을 결과 리스트에 추가
        while (i < left.size) {
            result.add(left[i])
            i++
        }

        while (j < right.size) {
            result.add(right[j])
            j++
        }

        return result.toTypedArray()
    }
}

3. 힙 정렬(Heap Sort)

완전 이진트리인 Heap 자료구조를 이용한 정렬방법

시간 복잡도

최선 최악 평균 모두 O(nlogn)

공간 복잡도

제자리 정렬이므로 O(1)

장점

시간 복잡도는 반드시 O(nlogn)을 보인다.
제자리 정렬이다.
자료에 따라 동작 시간이 크게 변하지 않는다.

단점

불안정정렬(Unstable Sort)이다.
속도가 퀵정렬보다 느릴 수 있다. 특히 자료가 거의 정렬된 상태에서는 느리다.
힙은 비선형구조이므로 캐싱효율이 낮아질 수 있다.

코틀린 코드

class HeapSort {
    fun heapSort(arr: Array<Int>) {
        val n = arr.size

        // 최대 힙으로 배열 변환
        for (i in n / 2 - 1 downTo 0) {
            heapify(arr, n, i)
        }

        // 힙에서 요소를 하나씩 꺼내서 정렬
        for (i in n - 1 downTo 0) {
            arr.swap(0, i) // 현재 루트(최댓값)를 배열 끝으로 보냄
            heapify(arr, i, 0) // 줄어든 배열에 대해 힙 구조 유지
        }
    }

    private fun heapify(arr: Array<Int>, 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.swap(i, largest)
            heapify(arr, n, largest)
        }
    }

    private fun Array<Int>.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}