[문제] 선택 정렬 구현하기

 

문제

반복문을 활용해 선택 정렬 알고리즘을 구현하세요.

selection_sort() 함수는 data를 파라미터로 받아 선택 정렬 알고리즘을 실행해 오름차순으로 정렬합니다.

이 함수는 리스트를 정렬할 뿐 어떤 값을 리턴하지는 않습니다.

실습 해설

선택 정렬은 쉽게 말해서 가장 작은 값을 찾아서 0번 인덱스에 넣고, 두 번째로 작은 값을 찾아서 1번 인덱스에 넣고, 세 번째로 작은 값을 찾아서 2번 인덱스에 넣는 식으로 반복하는 정렬 알고리즘입니다.

 

반복문 구조

조금 더 구체적으로 생각해 보죠. 선택 정렬을 하려면 다음과 같은 작업을 반복해야 합니다.

리스트 전체에서 가장 작은 값을 0번 인덱스에 옮기고, 범위를 좁혀서 1번 인덱스부터 마지막 인덱스까지 값들 중에서 가장 작은 값을 1번 인덱스에 옮기고, 다시 범위를 좁혀서 2번 인덱스부터 마지막 인덱스까지 값들 중에서 가장 작은 값을 2번 인덱스로 옮깁니다.

 

이 과정을 반복문으로 작성해 볼까요?

범위의 시작점이 0번 인덱스, 1번 인덱스, 2번 인덱스, …, len(data) - 1번 인덱스 이런 순서로 변할 테니까 반복 변수 i를 써서 for 반복문을 써 보면 다음과 같습니다.

반복문의 실행 부분에서는 현재 범위 안에서 가장 최솟값을 찾아서 값을 옮기면 될 겁니다.

for i in range(len(data)):
    # i부터 len(data)-1 범위 안에서 최솟값 찾아서 i번 인덱스로 옮기기

 

최솟값 구하기

그럼 i부터 len(data) - 1 범위에서 최솟값은 어떻게 찾을 수 있을까요?

가장 쉬운 방법은 최솟값을 변수에 저장해 놓고, 범위 안에 있는 값을 차례대로 비교하면서 만약 저장했던 최솟값보다 더 작은 값을 발견하면 최솟값을 교체하는 식으로 구할 수 있을 겁니다.

반복 변수 j를 써서 for 반복문을 써 보면 다음과 같이 할 수 있을 거예요.

일단 맨 처음 값인 data[i]를 최솟값 변수에 저장하고 차례대로 비교해 보겠습니다.

min_value = data[i]
for j in range(i + 1, len(data)):
    if data[j] < min_value:
        min_value = data[j]
# min_value는 최솟값

근데 우리한테 필요한 건 값이 아니라 인덱스입니다.

선택 정렬에서는 최솟값을 범위 맨 앞으로 옮겨야 하거든요. 그래서 최솟값이 있는 인덱스 min_index 라고 하고 코드를 고쳐 보면 다음과 같습니다.

min_index = i
for j in range(i + 1, len(data)):
    if data[j] < data[min_index]:
        min_index = j
# min_index는 최솟값이 있는 인덱스

 

중첩 루프 구조

선택 정렬에선 범위가 줄어들 때마다 최솟값을 구하고 그것의 위치를 범위 맨 앞으로 옮겨 줘야 합니다.

이렇게 구현하려면 범위를 줄이는 for 반복문(반복 변수 i를 쓰는 for 반복문)의 실행 부분에 최솟값을 구하는 코드를 써야 하는데요.

이렇게 반복문 안에 반복문을 쓰는 걸 중첩 루프 구조라고 해요.

for i in range(len(data)):
    min_index = i
    for j in range(i + 1, len(data)):
        if data[j] < data[min_index]:
            min_index = j
    # min_index는 최솟값이 있는 인덱스

최솟값을 구하는 범위는 i 값에 영향을 받죠? i 값이 바뀔 때마다 새롭게 최솟값을 구합니다.

그래서 범위가 바뀌면 min_index 값도 초기화하는데요, 바깥쪽 for 문의 실행 부분에서 min_index를 선언한 것도 주의 깊게 봐 주세요. 이 위치가 중요합니다.

혹시 이렇게 중첩 반복문을 만들고 min_index를 설정하는 내용이 잘 이해가 안 됐다면, 반드시 완전히 이해하고 넘어가는 걸 추천드립니다.

 

값 바꾸기

안쪽에 있는 for문이 끝나면 i부터 len(data) - 1 범위에서 최솟값이 있는 위치가 min_index에 저장돼 있을 겁니다.

이제 i에 있는 값과 min_index에 있는 값을 바꿔 주면 됩니다.

만약에 min_index의 값이 i로 그대로라면 값이 바뀌지 않고 그냥 넘어갈 겁니다.

def selection_sort(data):
    for i in range(len(data)):
        min_index = i
        for j in range(i + 1, len(data)):
            if data[j] < data[min_index]:
                min_index = j
        data[i], data[min_index] = data[min_index], data[i]

 

모법답안

def selection_sort(data):
    for i in range(len(data)):
        min_index = i
        for j in range(i + 1, len(data)):
            if data[j] < data[min_index]:
                min_index = j
        data[i], data[min_index] = data[min_index], data[i]

# 테스트 코드
list_1 = [9, 4, 2, 3, 1, 8, 1]
list_2 = [1, 2, 5, 2, 10, 16, 2]
list_3 = [10, 8, 6, 4, 2, 1]

selection_sort(list_1)
selection_sort(list_2)
selection_sort(list_3)

print(list_1)
print(list_2)
print(list_3)

공감과 댓글은 저에게 큰 힘이 됩니다.

 

Starting Google Play App Distribution! "Tester Share" for Recruiting 20 Testers for a Closed Test.

Tester Share [테스터쉐어] - Google Play 앱