선택정렬(Selection Sort)

데이터 배열을 내림차순 혹은 오름차순으로 나열하는 과정에서 사용되는 정렬 알고리즘이 존재합니다.
그 중에서 선택 정렬은 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬입니다.

(정리)
Index	Value
0	모든 값 중에서 가장 작은 값
1	첫번째 값(Index=0)을 제외하고 남은 값 중에서 가장 작은 값
…	…
i	i번째 부터 n-1 번째까지 값 중 가장 작은 값
…	…
n-2	n-2번째와 n-1 번째까지 값 중 가장 작은 값
n-1	마지막에 남은 하나의 값 (비교 대상 없음)
즉, 크기 n의 배열이 주어졌을 때, index 0부터 n-1까지의 모든 index i에 대해서, i번째 부터 n-1 번째까지 값 중 가장 작은 값을 구해서 index i에 놓으면 정렬된 배열을 얻을 수가 있습니다. 모든 index에 대해서 그 index에 위치시킬 값을 “선택”하기 때문에 이 정렬 알고리즘을 “선택 정렬”또는 “Selection Sort”이라고 부릅니다.

(예시)
1   9   4   6   11   10   3   15   2   13
#첫번 째는 가장 작은 숫자의 위치를 기억합니다. 1이 가장 작은 숫자인데 가장 좌측에 와있으므로 변하는 것이 없고, 그 다음 작은 2를 기억합니다.
1   2   4   6   11   10   3   15   9   13
#기억한 2를 1의 다음 위치로 넣어줍니다. 그리고 3의 위치를 기억합니다.
1   2   3   6   11   10   4   15   9   13 
#기억한 3을 3번째 위치로 넣어줍니다. 
. . .
1   2   3   4   6   9   10   11   13   15
#이렇게 반복을 하고나면 오름차순으로 나열이 됩니다.

장점과 단점

장점

코드가 직관적이기에 구현도 비교적 간단합니다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점이기에 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있는 정렬 방식입니다.
선택 정렬이 가장 적합한 자료 상태는 역순 정렬입니다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여줍니다.

단점

이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준다는 단점

파이썬 코드

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

복잡도

선택 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가집니다.
시간 복잡도는 우선 루프문을 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 하나의 루프에서는 현재 인덱스의 값과 다른 인덱스의 값들과 비교하여 최소값을 찾은 후 현재 인덱스에 있는 값과 상호 자리 교대를(swap)해야 해야하기 때문에 O(N)을 시간이 필요하게 됩니다. 따라서 선택 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.

참고

https://yjg-lab.tistory.com/160 선택 정렬
https://www.daleseo.com/sort-selection/