코틀린으로 퀵소트 구현하기 (QuickSort with Kotlin)
선택 정렬, 삽입 정렬, 퀵소트 등 정렬 기법은 이해하기 어려운 알고리즘은 아닌데, 조금만 잊고 살다 보면 구현하는 방법을 금새 잊어버린다. 리마인드 차원에서 코틀린으로 함 작성해봤다. QuickSort는 분할 정복 기법을 사용하는 대표적인 알고리즘이다. 알고리즘 설명은 어차피 유튜브가 짱이니까(?) 간략하게 작성한다.
- 리스트를 크게 1) 기준값, 2) 기준값보다 작은 녀석들, 3) 기준값보다 큰 녀석들 3개의 파로 분리한다.
- 2번과 3번 무리에 대해서 다시 한번 1) 기준값, 2) 기준값보다 작은 녀석들, 3) 기준값보다 큰 녀석들으로 분리하는 일을 반복한다.
- 이 과정이 반복되다보면 언젠가 리스트의 요소가 0 or 1개에 도달한다.
- 더 이상 분리시키는게 불가능 하므로, 0개 또는 1개짜리 리스트를 return 한다.
- 재귀함수의 호출 스택이 하나씩 pop 되면서
기준 값보다 작은 녀석들 + 기준 값 + 기준값보다 큰 녀석들이 하나의 리스트로 합쳐져서 return되기 시작한다. 그럼 이 리스트는 최종적으로 오름차순 정렬이 된다.
이 때 리스트를 기준값보다 작은 녀석들, 큰 녀석들로 분류하려면 일단 리스트를 첨부터 끝까지 한바퀴 돌아줘야 하니까 O(N)만큼의 시간이 소요된다.
시간복잡도 = 리스트를 3개의 파로 나누는 시간(=O(N)) * 쪼개는 과정을 반복하는 횟수(=호출 스택의 높이)
쪼개진 배열 사이즈가 0 or 1개가 될때까지 배열을 쪼개기 위해 함수의 호출 스택이 점점 쌓이게 되는데, 호출 스택의 높이는 기준값을 얼마나 센스있게 골랐는지에 따라 달라진다. 어느 한쪽으로 값이 치우치게 될수록 함수를 호출해야 하는 횟수가 늘어난다. 예를들어 10개짜리 리스트를 정렬하는데,
- 기준 값보다 작은 요소 : 음슴
- 기준 값보다 큰 요소 : 전체
이렇게 리스트를 극도로 편향되게 쪼개는 기준값을 고르는 일이 반복되면 호출 스택 크기는 10, 즉 O(N)이 된다. (이미 정렬된 배열에서 기준값을 제일 첫번째나 마지막 요소로 고르게 된다면 이렇게 될거다)
반대로 공평하게 반반으로 리스트를 쪼갤 수 있는 기준값을 골랐고, 이런 선택이 끝까지 반복된다면, 호출 스택은 4, O(log N)이 된다.
- 기준 값보다 작은 요소 : 절반
- 기준 값보다 큰 요소 : 절반
따라서 기준값을 아름답게 골랐을 경우 시간복잡도는 O(n * logn), 최악의 경우 O(n * n)이 된다.
일단 생각나는대로 두서없이 썼는데.. 아무도 이거 읽고 이해 못할듯 ㅋㅋㅠ
아무튼 코드를 보면 내 장황한 설명보다 훨씬 심플하다.
QuickSort with Kotlin
배열을 더이상 쪼갤 수 없을 때까지 3개의 무리로 쪼개고, 기준 값보다 작은 리스트 + 기준 값 + 기준값보다 큰 리스트로 합치는 과정이다. 코틀린 List는 파이썬처럼 + 연산자로 직관적인 배열 연산을 할 수 있어서 좋다.
fun qsort(list: List<Int>): List<Int> {
if (list.size < 2) {
return list
}
val pivot = list[list.size / 2]
val left = list.filter { it < pivot }
val right = list.filter { it > pivot }
return qsort(left) + listOf(pivot) + qsort(right)
}코드가 간결하고 이해가 잘되지만, 이 함수는 한번 호출될 때 마다 매번 새로운 리스트를 만들고 있다.
제자리 정렬을 사용해서 메모리를 좀 더 효율적으로 사용할 수 있다.
fun qsort(array: IntArray, left: Int = 0, right: Int = array.size - 1) {
val index = partition(array, left, right)
if (left < index - 1) {
qsort(array, left, index - 1)
}
if (index < right) {
qsort(array, index, right)
}
}
fun partition(array: IntArray, start: Int, end: Int): Int {
var left = start
var right = end
val pivot = array[(left + right) / 2]
while (left <= right) {
while (array[left] < pivot) {
left++
}
while (array[right] > pivot) {
right--
}
if (left <= right) {
val temp = array[left]
array[left] = array[right]
array[right] = temp
left++
right--
}
}
return left
}
