Algorithm(알고리즘) 기본 정렬(sort) 정리 feat. kotlin

1. selection sort(선택정렬)

/*
    선택 정렬.

    가장 작은것 선택하여 앞으로 이동 시킨다.
    직관적이고, 구현이 쉽다.
    비효율적이다.
    
    시간복잡도 O(N^2)
 */
 
val arr = intArrayOf(1, 10, 5, 3, 2, 4, 7, 9, 8, 6)

fun swap(a: Int, b: Int) {
    val temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp
}

fun selectionSort() {
    for (i in 0 until arr.size) {
        var selectedIdx = i
        for (j in i until arr.size) {
            if (arr[selectedIdx] > arr[j]) {
                selectedIdx = j
            }
        }
        swap(i, selectedIdx)
    }
}

fun main() {
    selectionSort()
    println(arr.joinToString(" "))
}

2. bubble sort (버블정렬)

/*
    버블 정렬.

    바로 옆에 있는 값과 비교하여 작으면 앞으로 보낸다.
    -> 가장 큰값이 가장 뒤로 간다.

    직관적이고, 구현이 쉽다.

    가장 비효율적이다.

    시간복잡도 O(N^2)
    * 선택정렬과 동일한 복잡도를 가지지만, swap 함수자체가 매우 자주 일어나기 때문에 더 비효율적이다.
 */


val arr = intArrayOf(1, 10, 5, 3, 2, 4, 7, 9, 8, 6)

fun swap(a: Int, b: Int) {
    val temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp
}

fun bubbleSort() {

    for (i in 0 until arr.size) {
        for (j in 0 until (arr.size - 1) - i) {
            if (arr[j] > arr[j + 1]) {
                swap(j, j + 1)
            }
        }
//        println(arr.joinToString(" "))
    }
}

fun main() {
    bubbleSort()
    println(arr.joinToString(" "))
}

3. insert sort (삽입정렬)

/*
    삽입 정렬

    자신보다 앞에 정렬된 원소들 사이에 적절한 위치에 삽입하여 정렬한다.
    "필요할때만, swap이 일어난다"

    앞쪽부터 정렬이 일어난다.

    선택, 버블, 삽입 셋다 O(N^2) 시간복잡도를 가지지만,
    이 셋중에서 가장 효율적이다.

 */


val arr = intArrayOf(10, 1, 5, 3, 2, 4, 7, 9, 8, 6)

fun swap(a: Int, b: Int) {
    val temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp
}

fun insertSort() {

    for (i in 1 until arr.size) {
        var j = i
        while (arr[j - 1] > arr[j]) {
            swap(j - 1, j)
            j -= 1

            if (j <= 0) break
        }
    }
}

fun main() {
    insertSort()
    println(arr.joinToString(" "))
}