선택 정렬(Selection Sort)의 개념

선택 정렬은 주어진 데이터 중에서 가장 작은 값부터 차례대로 선택하여 나열해 정렬하는 방식입니다. 입력 배열 전체에서 가장 작은 값을 선택한 후 제일 첫 번째에 위치시키고, 그 다음 작은 값을 찾아 두 번째에 위치시키고 .., 맨 마지막에 남은 두 개의 요소 중 가장 작은 값을 선택하여 위치하면 정렬이 완료됩니다.

선택 정렬의 Python 구현

Python 으로 선택 정렬을 아래와 같이 구현할 수 있습니다.

def selection_sort(arr: list) -> None:
    # 배열의 길이
    n = len(arr)

    # 배열을 순회하며
    for i in range(n):
        # 현재 위치를 최소값으로 가정
        min_index = i
        # 현재 위치 이후의 배열을 순회하며 최소값 탐색
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 찾은 최소값을 현재 위치로 이동
        arr[i], arr[min_index] = arr[min_index], arr[i]

이것은 어떻게 동작할까요? 아래와 같은 리스트를 정렬한다고 가정합시다.

[5, 12, 66, 19, 40]

맨 처음, 미정렬 부분의 첫 번째 원소는 최솟값으로 지정됩니다.

 ^
[5, 12, 66, 19, 40]

이후, “5” 라는 값과 나머지 4개의 값을 비교하며 가장 작은 값을 탐색합니다. 12, 66, 19 ,40 모두 5보다 큰 값이므로, 5가 정렬됩니다.

    ^
[5, 12, 66, 19, 40]

이제 12의 차례입니다. 12가 정렬되지 않은 부분들 중 가장 작은 값으로 지정되고, 66, 19, 40을 순회하며 더 작은 값을 찾습니다. 마찬가지로 12도 남은 부분들 중 가장 작은 값이므로 12를 정렬합니다.

        ^
[5, 12, 66, 19, 40]

이제 66이 가장 작은 값으로 지정됩니다. 19, 40을 순회하며 가장 작은 값을 찾는데, 가장 작은 값이 19이므로 19와 66은 자리가 바뀌어 정렬됩니다.

            ^
[5, 12, 19, 66, 40]

마찬가지로, 66이 가장 작은 값으로 지정되고, 나머지 40과 비교하여 더 작은 값을 찾아냅니다. 미정렬 부분 중에서는 40이 최솟값이므로, 66과 40의 자리를 바꾸어 정렬합니다.

# 완료
[5, 12, 19, 40, 66]

선택 정렬의 성능 분석과 특징

• 선택 정렬은 이중 루프로 구성됩니다. 바깥쪽 루프에서 모든 배열을 순회하고, 안쪽 루프에서는 정렬되지 않은 나머지 부분에서 최솟값을 찾기 위해 배열을 또 순회합니다. 따라서 선택 정렬은 O(N^2) 의 시간 복잡도를 가집니다.
• 선택 정렬은 데이터가 어떤 상태이든간에(완벽하게 정렬되어 있더라도, 무작위로 정렬되어 있더라도) 언제나 동일한 시간복잡도를 가집니다.
• 선택 정렬은 입력 배열의 크기 외에, 상수 개의 저장 공간만 필요합니다. 따라서 선택 정렬은 제자리 정렬 알고리즘입니다.
• 동일한 크기를 가진 데이터가 여러 개 있을 때, 정렬 후 상대적인 순서가 유지되지 않는 안정적이지 않은 정렬 알고리즘입니다.