[Kotlin] 코틀린으로 정렬 관련 문제를 풀 때 사용하는 배열이나 리스트를 정렬하는 메소드의 종류 및 각 메소드의 차이

목차

개요

기본적으로 코틀린에서는 배열도 객체로 취급되어 sort()와 같은 메소드를 사용할 수 있다. 그런데 이들 메소드들은 종류에 따라 약간의 차이가 있고, 메소드를 호출한 객체의 타입과 메소드의 종류에 따라 성능도 차이난다.

 

백준 - 수 정렬하기 5 문제를 푸는데 그냥 단순한 정렬 문제라고 생각했다가 정렬 메소드의 종류에 따라 TLE가 나기도 했고 AC가 나오기도 했다. 이들 메소드들 사이에 무슨 차이가 있길래 무엇을 쓰느냐에 따라 결과가 다르게 나타나는지 궁금해서 내부 구조를 확인해봤는데 생각보다 많은 차이가 있었다.

Kotlin 정렬 메소드의 종류

코틀린에서 배열이나 리스트를 정렬하는 메소드는 작동 방식과 결과 타입에 따른 3가지, 정렬 방법에 따른 3가지로 구분할 수 있다.

 

작동 방식과 결과 타입에 따른 구분

• sort()
• sortedArray()
• sorted()

 

정렬 방법에 따른 구분

• sort()
• sortWith()
• sortBy()

 

작동 방식과 결과 타입에 따른 구분은 다시 정렬 방법에 따른 메소드가 각각 존재하기 때문에 정렬 메소드는 총 9가지가 존재한다고 볼 수 있다. 예를 들어 sortedArray()와 sortWith()가 결합되면 sortedArrayWith()인 방식이다. 이 글에서는 작동 방식과 결과 타입에 따른 구분 위주로 다룰 것이다.

sort()

sort()는 원본 배열이나 리스트를 정렬한다. 원본 그 자체의 요소들을 정렬하기 때문에 배열은 상관없지만 리스트라면 mutableList에만 사용할 수 있다. 불변 리스트는 리스트의 요소들을 수정할 수 없기 때문이다.

 

sort()의 내부 구조는 다음과 같다.

배열의 sort(). 자바 Arrays의 sort()를 사용한다.

리스트의 sort(). 자바 Collections의 sort()를 사용한다.

여기서 배열의 경우에는 자바 Arrays의 sort()를 사용한다는 점으로 인해 아래와 같이 배열의 특정 구간만 정렬할 수도 있다.

val arr = intArrayOf(9, 8, 7, 6, 5, 4, 3, 2, 1)
arr.sort(3, 6)
println(arr.contentToString())

/*
[9, 8, 7, 4, 5, 6, 3, 2, 1]
*/

sortedArray()

sortedArray()는 이름에서 볼 수 있듯이 정렬된 배열을 반환한다. 이 메소드는 배열만 사용할 수 있는데, 원본 배열은 그대로 두고 원본을 복제한 새로운 배열을 정렬하여 반환한다.

 

sortedArray()의 내부 구조는 다음과 같으며, 원시배열(IntArray, DoubleArray 등, 자바의 원시타입 배열)이나 Array<T> 모두 같은 내용이 작성되어 있다.

원본을 먼저 복제한 후 정렬하여 반환한다.

sorted()

sorted()는 정렬된 List를 반환하는데, 사용할 수 있는 타입이 제한된 앞선 두 메소드와 달리 리스트를 비롯한 모든 Iterable 객체와 배열 모두가 사용할 수 있다. 이 역시 원본 객체는 그대로 두고 원본을 복제한 새로운 리스트를 정렬하여 반환한다.

 

그런데 이 메소드는 호출한 객체의 타입에 따라서 작동 방식에 차이가 있다.

 

먼저 일반적인 배열의 경우엔 다음과 같은 내부 구조를 갖는다.

이 경우에는 먼저 위의 sortedArray()로 얻은 정렬된 배열을 리스트로 변경하여 반환하는 것을 볼 수 있다.

 

두번째로 원시배열의 경우엔 다음과 같은 내부 구조를 갖는다.

 

세번째로 Iterable 객체의 경우엔 다음과 같은 내부 구조를 갖는다.

 

문제는 두번째와 세번째의 경우인데 두 경우 모두 toTypedArray()라는 메소드를 통해 배열로 변환하여 정렬하는 것을 볼 수 있다. 이 toTypedArray()가 문제가 되는데 그 내부 구조를 보면 다음과 같이 되어있다.

원시배열의 toTypedArray()

Iterable 객체가 Collection 객체일 때 호출되는 toTypedArray()

Collection 객체 중 한 종류인 List에서 구현되어 있는 toArray()

잘 보면 양쪽 모두 반복문을 통해 원본 객체를 배열로 변환하는 과정에서 원본 객체의 크기만큼의 시간이 더 걸리게 된다. Iterable 객체의 경우라면 그리 큰 문제가 아니지만, 원시배열은 문제가 조금 크다.

 

두번째와 같은 경우에는 배열이 Array<T> 타입으로 변환되는 것을 볼 수 있다. 이는 List와 같은 컬렉션 객체는 자바 원시타입을 요소로 가질 수 없기 때문이다. 결국 원시타입에 해당하는 타입의 배열은 각 요소를 wrapper 객체로 감싸주고 이를 정렬해야 하기 때문에 굉장히 비효율적인 방식이 된다.

 

실제로 Array<T>는 sortedArray()와 sorted()의 성능 차이가 거의 없으나, IntArray 등은 두 메소드의 성능 차이가 매우 크다. 1억개의 요소를 갖는 배열을 정렬해보면 다음과 같은 결과가 난다.

실제로는 배열을 초기화하는데 걸리는 시간까지 포함하면 Array<Int>의 두 정렬 메소드 모두 IntArray.sorted()와 비슷한 시간이 걸린다.

sort(), sortWith(), sortBy()

이 세가지는 정렬 기준에 따라 나뉜다. sort()는 기본적으로 오름차순으로 정렬하고 sortWith()는 람다 형태로 Comparator의 compare()를 구현한 메소드를 받아서 정렬하며, sortBy()는 파라미터로 받은 원본 배열이나 Iterable 객체에 담겨있는 객체 타입의 프로퍼티 등을 기준으로 오름차순으로 정렬하게 된다.

 

sort()와 sortBy()는 뒤에 Descending을 붙인 sortDescending()과 sortByDescending()으로 내림차순 정렬을 할 수 있다.

 

여기서 각 방법은 sortedArray()와 sorted()에도 동일하게 존재한다. 즉, sortedArrayWith()나 sortedBy() 등도 존재한다. 다만 sortedArrayBy()는 존재하지 않는다.

결론

정렬 관련 문제를 풀 때는 원시타입과 관련된 문제라면 Iterable 객체가 필요한 것이 아닌 이상에는 IntArray, DoubleArray 등의 원시배열에서 sort()나 sortedArray()를 사용하는 것이 좋을 것이다.

 

쓰고 보니 실제로는 원시배열을 정렬할 일은 거의 없을 것 같다는 생각이 들긴 하지만 정리해두면 언젠간 도움이 되지 않을까 싶다.