[알고리즘] 버블 정렬(Bubble Sort)

버블 정렬 정의

버블 정렬은 주어진 배열에서 인접한 두 개의 위치에 있는 데이터의 값을 비교하여 위치를 서로 교환하는 정렬 방식이다.

구현

package datastructure

fun main() {
    val list = mutableListOf(5, 8, 6, 2, 4)
    bubbleSort(list)
}

private fun bubbleSort(list: MutableList<Int>) {
    for(i in 0 until list.size - 1) {
        for(j in 0 until list.size - 1) {
            if(list[j] > list[j+1]) {
                swap(list, j, j+1)
            }
        }
        println("${i+1}회전: $list")
    }
}

private fun swap(list: MutableList<Int>, idx1: Int, idx2: Int) {
    val temp = list[idx1]
    list[idx1] = list[idx2]
    list[idx2] = temp
}

구현 결과

시간복잡도

정렬 과정을 보면, 각 회전마다 모든 데이터를 비교하는 것을 확인할 수 있다.

이를 구현하면 이중 for문을 사용해야 한다.

즉, O(n²)의 시간복잡도를 가지게 된다.