선택 정렬 (Selection Sort)

목표

• Selection Sort에 대해 설명할 수 있다.
• Selection Sort 과정에 대해 설명할 수 있다.
• Selection Sort를 Kotlin으로 구현할 수 있다.
• Selection Sort 의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다.

요약

Selection Sort는 원소를 넣을 위치를 지정해놓고 해당 위치에 넣을 원소를 선택하는 알고리즘이다.

Insertion Sort와 헷갈릴 수가 있는데 Insertion Sort는 한 원소를 정한 후에 해당 원소가 들어갈 위치를 탐색하는 것이고 Selection Sort는 위치를 지정하고 해당 위치에 넣을 원소를 탐색한다.

과정 (오름차순)

1. 주어진 배열 중에서 최소값을 찾는다.
2. 찾은 최소값을 첫 번째 위치와 값을 교체한다.
3. 첫 번째 위치에는 최소값이 위치해있기 때문에 제외하고 1번 과정을 반복한다.

Kotlin 코드

val lst = mutableListOf(1, 34, 5, 6, 78, 23, 56, 31, 64)

fun selectionSort() {
    for (i in 0 until lst.count() - 1) {
        var minVal = 0xffffff
        var minIdx = -1
        for (j in i until lst.count()) {
            if (minVal > lst[j]) {
                minVal = lst[j]
                minIdx = j
            }
        }
        lst[minIdx] = lst[i]
        lst[i] = minVal
    }
    print(lst)
}

시간 복잡도

1회차에서 n-1번 비교, 2회차에서 n-2번 비교, n-1번차에서 1번 비교하므로 식은 다음과 같이 표현할 수 있다.

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

Selection Sort는 미리 정렬되어 있는지의 여부와 상관 없이 2개의 원소를 대소 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)로 동일하다.

공간 복잡도

기존에 주어진 배열에서 원소 Swap만 이루어지므로 공간 복잡도는 O(n)이다.

특징

장점

1. 간단하게 구현이 가능하다.
2. 자료 이동 횟수가 미리 결정되어 있어 교환 횟수가 버블 정렬에 비해 적다.
3. 주어진 배열에서만 교환하므로 다른 메모리 공간이 필요하지 않다. => 제자리 정렬(in-place sorting)

단점

1. 시간 복잡도가 최선, 평균, 최악 모두 O(n^2)로 굉장히 비효율적이다.
2. 불안정 정렬이다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

Reference

• https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%84%A0%ED%83%9D%20%EC%A0%95%EB%A0%AC%20(Selection%20Sort).md#%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-selection-sort
• https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html