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

안녕하세요! 이번 포스팅에서는 코틀린을 이용한 코딩 테스트 문제 풀이에 대해 다뤄보겠습니다. 주제는 배열을 정렬하는 대표적인 방법인 버블 정렬(Bubble Sort)입니다. 본 강좌에서는 버블 정렬의 이론적인 배경과 코드를 다룰 예정입니다.

버블 정렬이란?

버블 정렬은 정렬 알고리즘 중 가장 간단한 형태로, 주어진 데이터의 가장 큰 수가 마지막으로 ‘표면으로 떠오른다’는 의미에서 ‘버블(Bubble)’이라는 이름이 붙었습니다. 이 방법은 배열을 여러 번 순회하면서 인접한 두 개의 요소를 비교하여 정렬하는 방식입니다.

버블 정렬의 작동 방식

  1. 배열의 첫 번째 요소와 두 번째 요소를 비교합니다.
  2. 만약 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다.
  3. 이 과정을 배열의 끝까지 반복합니다.
  4. 이 과정이 완료되면, 마지막 요소는 가장 큰 값으로 위치 고정됩니다.
  5. 위 과정을 정렬이 완료될 때까지 반복합니다.

버블 정렬의 시간 복잡도

버블 정렬의 최악의 경우 시간 복잡도는 O(n²)입니다. 이는 배열의 길이가 n일 때, n번의 반복에서 각 반복마다 n-1번의 비교가 이루어지기 때문입니다. 그러나 최선의 경우(이미 정렬된 경우)에는 O(n)의 시간 복잡도를 가집니다.

문제 설명

아래의 문제를 풀어 보겠습니다.

문제: 주어진 정수 배열을 버블 정렬 알고리즘을 사용하여 오름차순으로 정렬하세요.

문제 해결 과정

이제 문제를 해결하기 위해 코틀린 코드를 작성해 보겠습니다. 먼저 버블 정렬의 기본 로직을 정리합니다.

버블 정렬 구현하기


fun bubbleSort(arr: IntArray): IntArray {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            // 인접한 두 요소를 비교하여 정렬
            if (arr[j] > arr[j + 1]) {
                // 스와핑
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}
    

위 코드는 정수 배열을 입력받아 그것을 오름차순으로 정렬한 후 반환하는 함수입니다. 내부에 두 개의 for 문을 사용하여 배열을 순회하면서 요소들을 비교하고 위치를 서로 교환합니다.

실행 예시

이제 만들어진 함수를 호출하여 실제 정렬이 잘 이루어지는지 확인해 보겠습니다.


fun main() {
    val array = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("정렬 전 배열: ${array.joinToString(", ")}")
    val sortedArray = bubbleSort(array)
    println("정렬 후 배열: ${sortedArray.joinToString(", ")}")
}
    

위와 같은 코드를 실행하면 아래와 같은 결과를 얻을 수 있습니다.


정렬 전 배열: 64, 34, 25, 12, 22, 11, 90
정렬 후 배열: 11, 12, 22, 25, 34, 64, 90
    

버블 정렬의 최적화

기본적으로 구현된 버블 정렬 코드에서는 매 반복마다 배열의 끝까지 비교를 진행하는데, 이는 성능 개선에 비효율적일 수 있습니다. 따라서 어떤 개념을 통해 버블 정렬을 최적화할 수 있는지 살펴보겠습니다.

플래그 변수를 이용한 최적화

배열이 이미 정렬되어 있을 경우, 더 이상 반복할 필요가 없습니다. 이를 해결하기 위해 ‘스왑이 이루어졌는지 여부’를 기록하는 변수를 설정할 수 있습니다. 만약 한 번도 스왑이 이루어지지 않았다면, 배열이 정렬되었다고 판단할 수 있습니다.


fun optimizedBubbleSort(arr: IntArray): IntArray {
    val n = arr.size
    var swapped: Boolean
    for (i in 0 until n - 1) {
        swapped = false
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                swapped = true
            }
        }
        // 스와핑이 이루어지지 않았다면 반복 종료
        if (!swapped) {
            break
        }
    }
    return arr
}
    

최적화된 버전의 실행 예시


fun main() {
    val array = intArrayOf(64, 34, 25, 12, 22, 11, 90, 1, 2, 3, 4, 5)
    println("정렬 전 배열: ${array.joinToString(", ")}")
    val sortedArray = optimizedBubbleSort(array)
    println("정렬 후 배열: ${sortedArray.joinToString(", ")}")
}
    

위의 코드를 실행하면 다음과 같은 결과를 확인할 수 있습니다.


정렬 전 배열: 64, 34, 25, 12, 22, 11, 90, 1, 2, 3, 4, 5
정렬 후 배열: 1, 2, 3, 4, 5, 11, 12, 22, 25, 34, 64, 90
    

버블 정렬의 활용

버블 정렬은 간단한 정렬 알고리즘으로, 대체로 학습 목적이나 알고리즘 입문용으로 적합합니다. 하지만 대량의 데이터나 효율성이 중요한 상황에서는 퀵 정렬, 머지 정렬 등의 더 효율적인 알고리즘이 필요합니다.

마치며

이번 포스팅에서는 버블 정렬의 개념, 구현 방법, 최적화 기법에 대해 알아보았습니다. 알고리즘을 배우고 구현하는 과정에서 다양한 접근 방식을 시도해 보는 것은 매우 중요합니다. 다음 시간에는 다른 정렬 알고리즘에 대해 다루어보도록 하겠습니다.

감사합니다!