정렬 알고리즘[Merge Sort]

정렬알고리즘을 살펴보기전에 먼저 시간복잡도에 대해서 알아볼 필요가 있다

시간복잡도에 대한 내용을 정리했었어서 링크만 첨부하도록 하겠다

시간복잡도란?

간단하게 한줄로 요약해보면

시간복잡도란 "입력값과 연산수행시간의 상관관계를 나타내는 척도" 를 말한다

즉, "문제를 해결하는데 걸리는 시간과 입력의 합수관계"이다.

 

시간복잡도는 최악을 기준으로 "빅오 표기법"으로 표시하여 성능을 예측하는데,

시간복잡도가 빠른순으로 보면 아래와 같이 나타낼 수 있다

O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

O(1)이 시간복잡도가 가장 좋고(가장 빠르고), O(n^2)이 가장 안좋은것(가장 느림)을 알 수 있다

 

 

 

Merge sort 란?

이제 5개의 정렬알고리즘이 있는 표를 보면서 Merge Sort에 대해서 알아보자

 

Merge sort는 최선,평균이 O(n log n)이고, 최악의 경우에도 O(n log n)인것을 확인할 수 있다.

그리고 메모리는 O(n)인것을 확인할 수 있다

 

Merge sort는 하나의 배열 혹은 리스트를 두개의 균등한 크기로 분할하고 분할된 부분을 정렬한다음, 두 리스트를 합하여 전체가 정렬된 리스트로 만드는 방법이다. 이는 분할정복방법에 바탕을 두고있는데, 하나의 문제를 작은 2개의 문제로 분리하고 각각을 먼저 해결한뒤, 결과를 모아서 원래의 문제를 해결하는 전략이다.

만약 위 과정을 진행했는데, 문할된 문제가 아직도 충분히 작지않아서 해결하기 어렵다면, 분할정복방법으로 계속해서 모든 부분배열이 병합될때까지 적용하는 방식으로 진행한다. [이때 보통 순환호출(재귀적호출)을 사용 -> 함수 내부에서 자기자신을 또다시 호출하는 행위]

또한 Merge sort는 2의 거듭제곱을 기준으로 병합하는 특성이 있다

그치만, 부분배열을 위한 추가적인 메모리 공간이 필요하다는 단점이 존재한다.

 

Merge sort

 

 

 

예제를 통해 보기

백준 알고리즘 [수정렬하기 - 2750번]을 merge sort 알고리즘을 사용해서 풀어봤다

(https://www.acmicpc.net/problem/2750)

 

 

 

이 코드는 내장된 sorted 라이브러리를 사용해서 푼 기본적인 코드이다.

사실 이런 편한 sorted 라이브러리를 놔두고 굳이 알고리즘을 적용해서 풀 필요는 없지만 학습을 위해서 merge sort알고리즘을 사용해서 수정해봤다ㅎㅎ

fun main(){
    val reader = BufferedReader(InputStreamReader(System.`in`))
    println("줄의 개수를 입력하세요:")
    val n = reader.readLine().toInt()
    val list = mutableListOf<Int>()

    println("숫자를 입력하세요:")
    repeat(n) {
        list.add(reader.readLine().toInt())
    }

    println("결과:")
    val startTime = System.currentTimeMillis()  // 시간측정하기위해
    list.sorted()
        .forEach { println(it) }
    val endTime = System.currentTimeMillis()
    println("sorted() 수행 시간: ${endTime - startTime}")

    reader.close()
}

내장된 sorted() 라이브러리를 사용해서 푼 코드

 

 

 

list.sorted()로 사용해줬던 것을 merge sort 알고리즘을 사용해서 바꾼코드이다

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    println("줄의 개수를 입력하세요:")
    val n = reader.readLine().toInt()
    val list = mutableListOf<Int>()

    println("숫자를 입력하세요:")
    repeat(n) {
        list.add(reader.readLine().toInt())
    }

    println("결과:")
    val startTime = System.currentTimeMillis()  // 시간비교위해
    val sortedList = mergeSort(list)
    val endTime = System.currentTimeMillis()
    sortedList.forEach { println(it) }

    println("mergeSort 수행 시간: ${endTime - startTime}")
    reader.close()
}


// 리스트를 반으로 나누면서 정렬한뒤, 병합하는 정렬방식
fun mergeSort(arr: MutableList<Int>): MutableList<Int> {

    if (arr.size <= 1) {
        return arr
    }

    // 정렬된 리스트를 반으로 나눔
    val middle = arr.size / 2
    // 둘로 나눈것을 재귀적으로 정렬
    val left = arr.subList(0, middle).toMutableList()
    val right = arr.subList(middle, arr.size).toMutableList()

    return merge(mergeSort(left), mergeSort(right)) //정렬된 두 절반을 merge함수를 사용해 병합
}


// 두개의 정렬된 리스트(left,right)을 받아서, 하나의 정렬된 라스트로 병합
fun merge(left: MutableList<Int>, right: MutableList<Int>): MutableList<Int> {
    var leftIndex = 0
    var rightIndex = 0
    val result = mutableListOf<Int>()

    // 두 리스트를(left,right) 반복하면서 각 리스트에서 더작은거를 추가 (리스트중 하나가 소진될때까지 반복)
    while (leftIndex < left.size && rightIndex < right.size) {
        if (left[leftIndex] <= right[rightIndex]) {
            result.add(left[leftIndex])
            leftIndex++
        } else {
            result.add(right[rightIndex])
            rightIndex++
        }
    }

    // 소진되지 않은 리스트가 있다면, 요소를 비교해서 추가
    while (leftIndex < left.size) {
        result.add(left[leftIndex])
        leftIndex++
    }

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

    return result
}

mergeSort를 사용해서 푼 코드

 

 

 

수행시간이 뭐가 더 빠른지 궁금해서 출력해봤다

내장된 sorted() 라이브러리를 사용해서 푼 코드

 

mergeSort를 사용해서  푼 코드

 

 

 

Kotlin의 내장된 sorted()함수는 내부적으로 Timsort 알고리즘을 사용해서, 실용적인(실제)데이터일 경우에 수행속도가 더 빠른경우가 많다. 이는 Timsort가 부분적으로 정렬된 데이터에서 매우 효율적이고, 실용적인 데이터 집합에 대해 성능 최적화가 잘 되어 있기 때문이다.

그치만 특정한 상황이나 데이터 패턴에 따라 결과가 다를 수도 있음..! 지금 나온 결과처럼..