이번 강좌에서는 코틀린을 사용하여 버블 소트 알고리즘을 구현하는 방법을 알아보겠습니다. 버블 소트는 가장 간단하고 직관적인 정렬 알고리즘 중 하나로, 배열의 각 요소를 비교하고 교환하여 정렬하는 방식입니다. 이 강좌는 코딩 테스트를 준비하는 분들에게 유용할 것입니다.
버블 소트란?
버블 소트는 비교 기반의 정렬 알고리즘으로, 서로 인접한 두 요소를 비교하여 크기 순서에 맞지 않는 경우 교환하는 방식으로 작동합니다. 이 과정을 반복하여 모든 요소가 정렬될 때까지 진행합니다. 이 알고리즘의 시간 복잡도는 최악의 경우 O(n^2)이며, 안정 정렬입니다.
버블 소트의 작동 원리
버블 소트의 기본적인 작동 원리는 다음과 같습니다:
- 배열의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교합니다.
- 만약 첫 번째 요소가 두 번째 요소보다 크면 두 요소의 위치를 교환합니다.
- 배열 끝까지 이 과정을 반복합니다.
- 한 번의 패스가 끝나면 마지막 요소는 가장 큰 값이므로 정렬이 완료된 것입니다.
- 이 과정을 다시 처음부터 반복하며, 더 이상 교환이 필요 없을 때까지 진행합니다.
알고리즘 문제 정의
이제 버블 소트를 직접 구현해 보겠습니다. 주어진 정수 배열을 오름차순으로 정렬하는 코틀린 프로그램을 작성합니다.
문제
정수 배열
arr가 주어집니다. 이 배열을 버블 소트를 사용하여 오름차순으로 정렬하는 함수를 작성하세요.함수의 시그니처는 다음과 같습니다:
fun bubbleSort(arr: IntArray): IntArray
코틀린으로 구현하기
이제 문제를 해결하기 위해 코틀린에서 함수 bubbleSort()를 구현해 보겠습니다. 아래는 구현된 코드입니다:
fun bubbleSort(arr: IntArray): IntArray {
val n = arr.size
for (i in 0 until n - 1) {
// 최적화를 위한 플래그
var swapped = false
for (j in 0 until n - i - 1) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
val temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
swapped = true
}
}
// 만약 교환이 없었다면 이미 정렬된 상태
if (!swapped) break
}
return arr
}
코드 설명
위의 코드는 배열 arr를 입력받아 정렬된 배열을 반환합니다. 코드의 각 부분을 설명하겠습니다:
val n = arr.size: 배열의 크기를 저장합니다.- 두 개의
for루프를 사용하여 배열을 반복합니다. 외부 루프는 총n-1번의 패스를 수행하며, 내부 루프는 비교 작업을 담당합니다. swapped플래그는 현재 패스에서 교환이 발생했는지를 확인합니다. 만약 교환이 없었다면 배열은 이미 정렬된 것입니다.- 비교 후 두 요소의 위치를 교환하는 부분에서는 임시 변수를 사용하여 값을 스왑합니다.
- 교환이 없었던 경우에는 더 이상 반복하지 않고 루프를 종료합니다.
예제 테스트
이제 bubbleSort() 함수를 테스트해 보겠습니다. 다음은 몇 가지 테스트 케이스입니다:
fun main() {
val arr1 = intArrayOf(64, 34, 25, 12, 22, 11, 90)
println("정렬 전: ${arr1.joinToString(", ")}")
val sortedArr1 = bubbleSort(arr1)
println("정렬 후: ${sortedArr1.joinToString(", ")}")
val arr2 = intArrayOf(5, 1, 4, 2, 8)
println("정렬 전: ${arr2.joinToString(", ")}")
val sortedArr2 = bubbleSort(arr2)
println("정렬 후: ${sortedArr2.joinToString(", ")}")
}
테스트 결과
위의 main() 함수를 실행하면 다음과 같은 결과가 출력됩니다:
정렬 전: 64, 34, 25, 12, 22, 11, 90
정렬 후: 11, 12, 22, 25, 34, 64, 90
정렬 전: 5, 1, 4, 2, 8
정렬 후: 1, 2, 4, 5, 8
시간 복잡도 분석
버블 소트의 시간 복잡도를 분석해 보겠습니다:
- 최악의 경우:
O(n^2)– 배열이 역순으로 정렬되어 있는 경우. - 최선의 경우:
O(n)– 배열이 이미 정렬되어 있는 경우. 이때는 한 번의 패스 만으로 끝납니다. - 평균적인 경우:
O(n^2)
버블 소트는 삽입 정렬과 같은 간단한 정렬 알고리즘에 비해 비효율적이며, 대규모 데이터에 대해서는 잘 사용되지 않습니다. 하지만 이해하고 구현하기 쉽기 때문에 알고리즘 기초 학습에 적합합니다.
마무리
이번 강좌에서는 코틀린을 사용하여 버블 소트 알고리즘을 구현해 보았습니다. 버블 소트는 비교 기반의 정렬 알고리즘으로, 이해하기 쉽고 직관적입니다. 코딩 테스트에서 자주 출제되는 주제 중 하나인 만큼, 반복적으로 연습해 보시기 바랍니다.
연습 문제
자신의 버블 소트 구현을 개선하거나 다양한 테스트 케이스를 만들어 보세요. 다음과 같은 문제도 도전해 보실 수 있습니다:
- 주어진 배열을 내림차순으로 정렬하는 함수 작성하기.
- 버블 소트의 시간을 측정하여 다양한 입력 크기에서 성능 비교하기.
- 버블 소트를 재귀적으로 구현해 보기.
이 외에도 다양한 정렬 알고리즘에 대한 학습을 통해 알고리즘에 대한 깊은 이해를 가져보시기 바랍니다. 감사합니다!