WooVictory/Ready-For-Tech-Interview

로직

  1. 1회전에 첫번째 원소와 두번째 원소, 2회전에 두 번째 원소와 세 번째 원소를, 이런식으로 마지막에서 두번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
  2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회정에서는 맨ㅈ끝에 있는 원소를 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 원소 까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어남
fun main() {
    val array = intArrayOf(6, 2, 1, 3, 4, 5)

    val arraySize = array.size
    for(i in array.indices) {
        for(j in 0 until arraySize -i -1) {
            if(array[j] > array[j+1]) swap(array, j, j+1)
        }
    }

    array.forEach {
        print("$it ")
    }
}

private fun swap(array: IntArray, from: Int, to: Int) {
    val temp = array[from]
    array[from] = array[to]
    array[to] = temp
}

시간복잡도

정렬이 되어있건, 안되어있건 2개의 원소를 비교하기 때문에 모든 경우세서 시간복잡도가 O(N^2)으로 동일하다.

공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

장점