[알고리즘] 선택 정렬(Selection Sort) in Python

정렬 알고리즘에서 두 번째로 배워 볼 것은 선택 정렬이다. 선택 정렬은 어떻게 동작하는지 알아 보고 실제 코드로 구현해 보자.

 

📌 정의

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
선택 정렬은 리스트(배열)의 정렬되지 않은 부분에서 가장 작은(혹은 가장 큰) 요소를 반복적으로 선택하여, 리스트의 정렬된 부분으로 옮기는 방식의 간단하고 효율적인 정렬 알고리즘이다.

Selection Sort Algorithm - GeeksforGeeks

 

📌 동작 과정

아래의 이미지를 보면, 파란색 박스는 현재 위치이고, 빨간색 박스는 범위에서의 최솟값을, 노란색 박스는 정렬된 범위를 가리킨다.

1. 정렬되지 않는 범위(파랑)를 돌면서 그 중 최솟값(빨강)을 찾아서 정렬되지 않은 범위의 맨앞으로 옮기는 과정을 반복한다.
2. 1번을 반복하면 정렬된 범위(노랑)가 늘어나면서 정렬이 완료된다.

선택 정렬의 동작 과정

 

📌 구현 (in Python)

1. 처음에 정렬되지 않은 범위의 맨앞을 최솟값으로 할당한다
2. 범위를 돌면서 더 작은 값이 있으면 최솟값을 업데이트 한다.
3. 정렬되지 않은 범위의 맨앞과 최솟값의 위치를 교환한다.
4. 2~3번을 반복한다.

동작 과정 1, 2번을 보면 이중 반복문이 필요한 것을 알 수 있다.

 

# 선택 정렬 함수 정의
def selection_sort(array):
    n = len(array) # 배열의 길이를 n으로 할당

    for i in range(n): # 현재 교환할 인덱스로 i를 할당
        min_index = i # 처음에는 정렬되지 않은 가장 맨앞의 요소를 최솟값으로 할당

        for j in range(i + 1, n): # i와 비교할 인덱스로 j를 할당

            if array[j] < array[min_index]: # 현재 인덱스의 값이 최솟값보다 작을 경우
                min_index = j  # 최솟값 업데이트

        # 한 번 범위를 모두 돌았으면 범위의 가장 맨앞과 최솟값을 서로 교환
        array[i], array[min_index] = array[min_index], array[i]

        # print(array) # 정렬되는 과정 출력

    return array # 정렬된 배열 반환

# 테스트 코드
if __name__ == "__main__":
    array = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] # 임의의 배열 할당
    print(f"BEFORE SELECTION SORT: {array}") # 정렬되지 않은 배열 화면 출력
    selection_sort(array) # 선택 정렬 함수 실행
    print(f"AFTER SELECTION SORT: {array}") # 정렬된 배열 화면 출력

BEFORE SELECTION SORT: [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
AFTER SELECTION SORT: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

위의 코드 중에서 아래의 각주를 해제하고 함수를 돌려보면 아래의 과정을 볼 수 있다.

# print(array) # 정렬되는 과정 출력

# 처음의 배열
[8, 5, 2, 6, 9, 3, 1, 4, 0, 7]

# 반복문을 돌며 정렬되어 가는 배열
[0, 5, 2, 6, 9, 3, 1, 4, 8, 7]
[0, 1, 2, 6, 9, 3, 5, 4, 8, 7]
[0, 1, 2, 6, 9, 3, 5, 4, 8, 7]
[0, 1, 2, 3, 9, 6, 5, 4, 8, 7]
[0, 1, 2, 3, 4, 6, 5, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

반복문을 거듭할수록 왼쪽에서부터 정렬이 되어가는 걸 알 수 있다.