선택 정렬(Selection Sort) 알고리즘

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

선택 정렬(Selection Sort)?

기준 좌표를 설정하고 해당 좌표부터 마지막 원소까지 탐색하여 최소(대)값 좌표를 찾는다. 이후 기준 좌표의 값과 치환이 결정된 좌표의 값과 서로 교환하여 정렬하는 알고리즘이다. 치환이 결정된 좌표값만을 찾아 치환하는 방식으로 추가 메모리를 요구하지 않는 제자리 정렬에 해당한다.

선택 정렬 동작

위 그림의 배열을 정렬한다고 해보자.

총 n-1단계에 걸쳐 차례대로 $n-1,\ n-2, \cdots,\ 1$개의 원소들 중 최소(대)값을 탐색하여 치환하므로 전체 탐색 횟수는 $\cfrac{n(n-1)}{2}$이고 그에 따른 시간복잡도는 $O(n^2)$이다.

python 코드

def selection(arr):
    for i in range(len(arr) - 1):
        m = i
        for j in range(i, len(arr)):
            if m > arr[j]:
                m = j
        arr[i], arr[m] = arr[m], arr[i]
    return arr

a = [3, 1, 2, 5, 4, 6]
b = [6, 5, 4, 3, 2, 1]
c = [5, 5, 3, 3, 1, 1]
print(f'selection a:{selection(a)}, b:{selection(b)}, c:{selection(c)}')