이 글은 나동빈님의 "이것이 코딩테스트다 with 파이썬"책과 유튜브 강의를
교재로 삼아 공부한 후 나의 이해한 내용을 정리한 글입니다

선택 정렬

핵심 아이디어

정렬할 요소를 탐색하며 가장 작은 값을 찾아 '선택'하여 범위의 맨 앞으로 보낸다

정렬 진행 방식

1 ) 정렬할 배열을 탐색하며 가장 작은 값을 찾아서 선택하여 맨 앞으로 보낸다
2 ) 맨 앞으로 보낸 요소를 제외한 나머지 요소를 다시 탐색하여 1)의 과정을 시행한다
3 ) 정렬할 배열의 탐색을 완료 할 때 까지 1),2)의 과정을 반복하여 시행한다
4 ) 정렬 완료

기본 코드 구조

def f_select(arr):
    for i in range(len(arr)):
        min_num = 9999
        index_num = 0
        for j in range(i, len(arr)):
            if min_num > arr[j]:
                min_num = arr[j]
                index_num = j
        temp = arr[i]
        arr[i] = min_num
        arr[index_num] = temp
    return arr

코드 설명

선택정렬은 정렬할 요소를 탐색하며, 범위 중 가장 작은 값을 찾아야 하는 정렬 알고리즘이다.

따라서 반복문과 '작은 값'을 판단 해 줄 기준요소가 필요하다.
(여기서 "작은 값"을 판단 해줄 기준 요소는 탐색하는 범위 내에서 계속 갱신된다)

코드 1

def f_select(arr):
    for i in range(len(arr)):
    	min_num = 9999
        index_num = 0

코드 1에서 작성 한 것처럼 주어진 배열의 인덱스를 탐색하는 for문을 생성 한 후, min_num과 index_num이라는 변수를 생성했다.

여기서 min_num이란 위에서 언급한 "작은 값"의 기준 역할을 해 줄 변수이고,
index_num이란 주어진 배열에서 min_num의 값의 인덱스를 표현하는 변수이다.

코드 2

for j in range(i, len(arr)):
   if min_num > arr[j]:
      min_num = arr[j]
      index_num = j

주어진 배열을 탐색하는 for문 안에 추가적인 for문을 설정했다.
선택정렬은 주어진 범위에서 "작은 값"을 찾아 맨 앞으로 보내는 방식이기 때문에 이미 맨 앞으로 보낸 값을 다시 탐색할 이유가 없기에 범위를 (i, len(arr)) 로 설정 하였다.

그리고 for문 내부에 "만약에 min_num이 주어진 배열의 j 인덱스의 값보다 작다면" 이라는 조건문을 삽입 하였다.
위에서 설정한 min_num이라는 변수는 사실상 현재 가장 작은 값을 의미한다.
즉 위의 조건문을 해석하면

"현재 설정되어 있는 최솟값보다 현재 배열을 탐색하는 요소의 값이 더 작다면"
min_num을 현재 탐색하는 요소의 값으로 갱신하고, 해당 요소의 인덱스 값을 index_num이라는 변수에 담는다. 라는 의미의 코드이다.

코드 3

temp = arr[i]
arr[i] = min_num
arr[index_num] = temp

코드 2의 과정까지 마치고 나면 두 번째 for문을 탈출 한 후 첫 번째 for문의 마지막 실행코드로 넘어간다.

즉 설정한 범위의 배열 요소를 모두 탐색 한 후이므로 min_num은 배열의 가장 작은 값(최솟값)으로 갱신 되어 있는 상태이다.

이제 선택정렬의 마지막 과정인 가장 앞으로 보내야 한다.
여기서 가장 앞이란 현재 탐색하는 배열의 범위의 가장 앞을 뜻한다.
temp라는 변수를 선언한 뒤, 현재 탐색하는 i(탐색 범위의 시작점)의 값을 할당한다.
그리고 i의 값을 위 코드 2에서 갱신한 min_num, 최솟값으로 재할당한다.
최종적으로 min_num이 있던 자리에 위에서 설정한 temp (arr[ i ])을 할당하여 두 값의 자리를 바꾸면 과정 한 번이 완료 된다.

이 과정을 for문이 종료될때까지 반복하면 정상적으로 오름차순 정렬이 완료된다.

최종 코드 // 입 출력 값

arr = [16, 7, 12, 11, 8, 10, 9, 15, 13, 14]

def f_select(arr):
    for i in range(len(arr)):
        min_num = 9999
        index_num = 0
        for j in range(i, len(arr)):
            if min_num > arr[j]:
                min_num = arr[j]
                index_num = j
        temp = arr[i]
        arr[i] = min_num
        arr[index_num] = temp
    return arr

print(f_select(arr))

==> [7, 8, 9, 10, 11, 12, 13, 14, 15, 16]