[Kotlin] 정렬 2 (병합정렬, 퀵정렬)

1. 병합정렬 (Merge Sort)

배열을 균등한 크기의 두 배열로 나누어 분할된 각 배열을 정렬한 다음 합하여  정렬하는 형태이다.

재귀함수와 분할정복을 사용하여 구현한다.

정렬은 항상 느끼지만 글로 설명하는 것 보단 아래 애니메이션을 통해 직접 동작을 확인하는 것이 이해가 빠른 것 같다.

병합정렬 Kotlin Code

 

// mergedList = split(arr)

fun split(arr: ArrayList<Int>): ArrayList<Int> {

    if (arr.size <= 1) return arr

    val middle = arr.size / 2

    // 재귀함수를 통해 left, right split 및 sort하여 merge
    val left = split(ArrayList(arr.subList(0, middle)))
    val right = split(ArrayList(arr.subList(middle, arr.size)))

    return merge(left, right)
}

private fun merge(left: ArrayList<Int>, right: ArrayList<Int>): ArrayList<Int> {
    val mergedList = arrayListOf<Int>()
    var leftIndex = 0
    var rightIndex = 0

    // Case 1 : left, right 모두 존재
    while (leftIndex < left.size && rightIndex < right.size) {
        if (left[leftIndex] < right[rightIndex]) {
            mergedList.add(left[leftIndex])
            leftIndex++
        } else {
            mergedList.add(right[rightIndex])
            rightIndex++
        }
    }

    // Case 2 : right만 존재
    while (rightIndex < right.size) {
        mergedList.add(right[rightIndex])
        rightIndex++
    }

    // Case 3 : left만 존재
    while (leftIndex < left.size) {
        mergedList.add(left[leftIndex])
        leftIndex++
    }
    return mergedList
}

 

split(array)

인자로 받은 array에 대한 분할을 수행한다.

그 후 merge(left, right)를 return 하여 분할된 left, right array에 대한 정렬 + 병합을 수행한 array를 반환한다.

이 때, 재귀함수를 통해 다시 split을 호출하여 각 left, right array에 대해 더 이상 나눌 수 없을 때 까지 분할하여 최하위 부분 배열부터 정렬 + 병합을 수행하여 최종 정렬된 array를 return 한다.

 

merge(left, right)

인자로 받은 left, right array에 대해 값을 비교하여 두 배열을 정렬 + 병합한다.

이 때, left, right의 값을 각각의 pointer를 가지고 비교하며, 두 값 중 더 작은 값을 mergedList에 삽입한다.

한 쪽의 배열이 모두 mergedList에 들어가 비워졌다면, 남은 배열의 모든 값을 mergedList에 삽입하고 return한다.

 

시간 복잡도 : 

각 분할 단계 별 시간 복잡도는 O(n)을 가짐.

단계는 항상 log n만큼 만들어지므로 시간 복잡도는 O(n log n)

 

 

 

 

 

 

2. 퀵정렬 (Quick Sort)

기준점 (pivot)을 정해 기준점의 값보다 작은 값은 left array, 큰 값은 right array에 저장한다.

각 left, right array에 대해서는 재귀함수를 통해 같은 동작을 반복하여 정렬한다.

최종적으로 left, pivot, right 순으로 차례로 병합하여 정렬된 array를 리턴한다.

 

 

퀵정렬 Kotlin Code

fun quickMerge(arr: ArrayList<Int>): ArrayList<Int> {

    if (arr.size <= 1) return arr

    // index의 처음 값 pivot 설정
    val pivot = arr.removeFirst()

    val left = arrayListOf<Int>()
    val right = arrayListOf<Int>()

    for (i in arr.indices) {

        // pivot과 배열의 각 값 비교하여 left or right 배열에 추가
        if (arr[i] > pivot) {
            right.add(arr[i])
        } else {
            left.add(arr[i])
        }
    }

    val mergedList = arrayListOf<Int>()

    // 재귀함수를 통해 정렬된 left, right 배열 left + pivot + right 순으로 merge
    mergedList.addAll(quickMerge(left))
    mergedList.add(pivot)
    mergedList.addAll(quickMerge(right))
    return mergedList
}

array의 처음 값을 pivot으로 설정한다. pivot으로 설정된 값은 array에서 제거한다.

array를 순회하며 pivot보다 작은 값은 left array, 큰 값은 right array에 저장한다.

재귀함수를 통해 다시 quickMerge 메소드를 호출하며 모든 값에 대해 정렬을 수행하고, left + pivot + right으로 병합되어 정렬된 배열로 만든다.

 

 

시간 복잡도 : 

병합 정렬과 유사하게 O(n log n).

그러나 완전 정렬 된 경우에서 pivot이 가장 크거나 작은 값을 가지는 경우, left 또는 right에 값이 모두 몰리게 되어

최악의 경우 O(n^2)이 됨.

 

 

참고, gif 출처 :

 

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

https://www.learnsimpli.com/quick-sort-algorithm-introduction-performance/

Quicksort algorithm in Javascript