Kotlin 연습하기(5) - 버블정렬

정렬이란 무엇일까?

정렬(sorting)은 데이터 (예: 숫자, 문자열 등)를 일정한 순서대로 나열하는 과정이다. 예를 들어, 시험 점수가 섞여 있을 때 낮은 점수부터 높은 점수 순서대로 정렬하면, 누구의 점수가 가장 낮고 누구의 점수가 가장 높은지 쉽게 알 수 있다.

 

왜 정렬이 필요할까?

• 검색 : 정렬된 데이터를 빠르게 검색할 수 있다.
• 분석 : 데이터를 정리해서 보고서나 그래프로 만들 때, 정렬된 상태가 더 유용하다.
• 문제 해결 : 코딩 테스트나 알고리즘 문제에서 정렬은 자주 사용되는 기본 기술이다.

 

버블 정렬(Bubble Sort) 이해하기

 

버블 정렬의 원리 

• 버블 정렬은 인접한 두 개의 원소를 비교하여 순서가 맞지 않으면 서로 교환한다.
• 한 번의 반복(패스)마다 가장 큰 값이 맨 뒤로 이동하게 된다.
• 이 과정을 전체 배열이 정리될 때까지 반복한다.

 

버블 정렬 알고리즘의 단계별 설명

1. 배열의 첫 번째와 두 번째 요소를 비교한다. 만약 첫 번째가 두 번째보다 크다면 서로 교환한다.
2. 두 번째와 세 번째 요소를 비교하고, 필요하면 교환한다.
3. 배열 끝까지 이 과정을 반복하면, 한 번의 반복 후 가장 큰 값이 배열의 끝으로 이동한다.
4. 배열의 크기만큼 (또는 더 적은 횟수로) 반복하여 전체 배열을 정렬한다.

버블 정렬의 단점 

• 비교와 교환이 반복되기 때문에, 데이터가 많을 경우 시간이 많이 걸린다. 시간복잡도 O(n^2)

버블 정렬 예제 코드

// 버블 정렬 함수: 배열을 오름차순으로 정렬
fun bubbleSort(arr: Array<Int>): Array<Int> {
    // 배열의 길이를 저장합니다.
    val n = arr.size
    // 전체 배열을 n-1번 반복합니다.
    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
                // 교환 후 로그 출력 (각 단계별 상태 확인)
                println("교환 후 배열 상태: ${arr.joinToString(", ")}")
            }
        }
    }
    return arr
}

fun main() {
    val numbers = arrayOf(64, 34, 25, 12, 22, 11, 90)
    println("원래 배열: ${numbers.joinToString(", ")}")
    val sortedNumbers = bubbleSort(numbers)
    println("정렬된 배열: ${sortedNumbers.joinToString(", ")}")
}

 

실행 결과

원래 배열: 64, 34, 25, 12, 22, 11, 90
교환 후 배열 상태: 34, 64, 25, 12, 22, 11, 90
교환 후 배열 상태: 34, 25, 64, 12, 22, 11, 90
교환 후 배열 상태: 34, 25, 12, 64, 22, 11, 90
교환 후 배열 상태: 34, 25, 12, 22, 64, 11, 90
교환 후 배열 상태: 34, 25, 12, 22, 11, 64, 90
교환 후 배열 상태: 25, 34, 12, 22, 11, 64, 90
교환 후 배열 상태: 25, 12, 34, 22, 11, 64, 90
교환 후 배열 상태: 25, 12, 22, 34, 11, 64, 90
교환 후 배열 상태: 25, 12, 22, 11, 34, 64, 90
교환 후 배열 상태: 12, 25, 22, 11, 34, 64, 90
교환 후 배열 상태: 12, 22, 25, 11, 34, 64, 90
교환 후 배열 상태: 12, 22, 11, 25, 34, 64, 90
교환 후 배열 상태: 12, 11, 22, 25, 34, 64, 90
교환 후 배열 상태: 11, 12, 22, 25, 34, 64, 90
정렬된 배열: 11, 12, 22, 25, 34, 64, 90