코틀린 코딩테스트 강좌, 퀵 정렬

퀵 정렬(Quick Sort)은 매우 효율적인 정렬 알고리즘으로, 특히 평균적인 경우에 O(n log n)의 시간 복잡도를 가지며, 공간 복잡도는 O(log n)입니다. 이 글에서는 퀵 정렬의 개념, 코틀린 구현 방법, 알고리즘 문제, 문제 해결 과정 등을 자세히 살펴보겠습니다.

1. 퀵 정렬의 개념

퀵 정렬은 분할 정복 알고리즘의 하나로, 다음과 같은 단계로 동작합니다:

  1. 주어진 배열에서 하나의 원소를 피벗(pivot)으로 선택합니다. 보통 배열의 첫 번째 원소, 마지막 원소, 또는 중앙 원소를 선택합니다.
  2. 배열을 피벗을 기준으로 두 개의 부분 배열로 나눕니다. 피벗보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 위치하도록 합니다.
  3. 왼쪽과 오른쪽의 부분 배열에 대해 재귀적으로 퀵 정렬을 적용합니다.

이 과정은 배열이 더 이상 나눌 수 없을 때까지 반복됩니다. 퀵 정렬의 가장 큰 장점은 평균적으로 매우 빠르며, in-place 정렬 알고리즘이라는 것입니다. 따라서 추가적인 메모리 사용량이 적습니다.

2. 퀵 정렬의 동작 예시

정렬할 배열이 [3, 6, 8, 10, 1, 2, 1]이라고 가정해 보겠습니다. 다음은 퀵 정렬의 단계별 과정입니다.

Step 1: 피벗 선택

피벗: 1

Step 2: 배열 분할

[1, 2, 1, 10, 6, 8, 3]

Step 3: 재귀 호출

  • 왼쪽 배열 [1, 1]은 이미 정렬됨.
  • 오른쪽 배열 [10, 6, 8, 3]에 대해 다시 퀵 정렬을 적용.

Step 4: 최종 정렬

[1, 1, 2, 3, 6, 8, 10]

3. 알고리즘 문제

이제, 퀵 정렬을 활용하여 정렬된 배열을 반환하는 문제를 해결해 보겠습니다.

문제: 주어진 정수 배열을 퀵 정렬을 사용해 정렬하라.

입력: [10, 7, 8, 9, 1, 5]

출력: [1, 5, 7, 8, 9, 10]

4. 코틀린 구현

아래는 위 문제를 해결하기 위한 코틀린 코드입니다.


fun quickSort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        val pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = (low - 1)

    for (j in low until high) {
        if (arr[j] <= pivot) {
            i++
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }

    val temp = arr[i + 1]
    arr[i + 1] = arr[high]
    arr[high] = temp
    return i + 1
}

fun main() {
    val arr = intArrayOf(10, 7, 8, 9, 1, 5)
    quickSort(arr, 0, arr.size - 1)
    println("정렬된 배열: ${arr.joinToString(", ")}")
}

5. 코드 설명

5.1 quickSort 함수

quickSort 함수는 재귀적으로 호출되며, 배열의 시작 인덱스와 끝 인덱스를 인자로 받습니다. 만약 시작 인덱스가 끝 인덱스보다 작은 경우, partition 함수를 호출하여 피벗의 위치를 찾고, 이를 기준으로 배열을 다시 정렬합니다.

5.2 partition 함수

partition 함수는 배열을 피벗을 기준으로 분할하는 역할을 합니다. 모든 원소를 확인하며, 피벗보다 작은 원소를 왼쪽 배열로 이동시킵니다. 마지막으로 피벗을 올바른 위치에 배치하고 그 인덱스를 반환합니다.

6. 복잡도 분석

퀵 정렬의 시간 복잡도는 다음과 같습니다:

  • 최선의 경우: O(n log n)
  • 평균 경우: O(n log n)
  • 최악의 경우: O(n2) – 이 경우는 이미 정렬된 배열을 입력으로 주었을 때 발생할 수 있습니다.

공간 복잡도는 O(log n)입니다. 재귀 호출로 인한 스택 메모리 사용 때문입니다.

7. 결론

이 글에서는 코틀린으로 퀵 정렬 알고리즘을 구현하는 방법을 살펴보았습니다. 퀵 정렬은 그 효율성과 간결함 덕분에 많은 상황에서 사용됩니다. 코딩 테스트와 같은 상황에서도 자주 등장하는 문제이므로, 기본적인 이해와 연습은 매우 중요합니다.

8. 추가 연습 문제

아래는 퀵 정렬을 응용할 수 있는 몇 가지 추가 연습 문제입니다:

  • 배열의 k번째 작은 원소를 찾는 방법을 구현해보세요.
  • 퀵 정렬을 비재귀적으로 구현해보세요.
  • 정렬된 두 배열을 병합하는 문제를 해결해보세요.

퀵 정렬은 알고리즘과 데이터 구조의 여러 중요한 개념을 배울 수 있는 좋은 방법입니다. 계속해서 연습하고, 이해를 깊이 있는 지식으로 확장하시기 바랍니다.