선택 정렬 (selection sort)
- 선택 정렬 (selection sort) 알고리즘을 이용하여 정수 리스트를 받으면 오름차순으로 정렬해주는 함수 만들기
- 리스트에서 최소값을 찾는다.
- 최소값과 리스트의 맨 앞에 있는 값과 위치를 바꾼다.
- 맨 앞에 있는 값을 제외한 나머지 리스트에서 위의 과정을 반복한다.
1. 리스트에서 최소값 찾기
리스트에서 최소값을 찾는 과정을 하나 하나 살펴보면 아래와 같음.
- 아래와 같은 리스트가 있다고 하자.
list = [2, 4, 3, 5, 1, 7, 9]
- 먼저 list의 첫 번째 항목 list[0]과 두 번째 항목 list[1] 비교한다.
1라운드
list[0]
|
list = [2, 4, 3, 5, 1, 7, 9]
|
list[1]
- list[0]이 list[1]보다 작은 경우 그 다음 값과 비교한다. 즉, 작은 숫자가 이기는 1:1 싸움을 순차적으로 걸어서 우승자만 살아남는 방식이다.
1라운드
list[0]승
|
list = [2, 4, 3, 5, 1, 7, 9]
|
list[1]패
1라운드
list[0]승
|
list = [2, 4, 3, 5, 1, 7, 9]
|
list[2]패
- list[0]보다 더 작은 값과 비교될 때 까지 이 과정을 반복한다. (우승자가 계속 살아남음.)
1라운드
list[0]승
|
list = [2, 4, 3, 5, 1, 7, 9]
|
list[3]패
- list[0]이 어느 값보다 큰 경우(기존 우승자를 이긴 새로운 우승자가 나타난 경우.)
1라운드
list[0]패
|
list = [2, 4, 3, 5, 1, 7, 9]
|
list[4]승
아래와 같이 비교 대상을 바꿔준다. 즉, 새로운 우승자와 다른 숫자들과 싸움을 붙임.
새로운 우승자가 기존 우승자와 싸웠던 상대들과 다시 싸울 필요는 없다.
1라운드
list[5]패
|
list = [2, 4, 3, 5, 1, 7, 9]
|
list[4]승
- list[4]가 첫 번째 라운드의 최종 우승자 즉, 최소값으로 판명되었다.
1라운드
list[5]패
|
list = [2, 4, 3, 5, 1, 7, 9]
|
list[4]승-최종우승
2. 최소값과 리스트 맨 앞의 값의 자리 바꾸기
- 최종 우승자는 1등석을 차지하게 된다.
1라운드
기존 1등석
|
list = [1, 4, 3, 5, 2, 7, 9]
|
최종우승자
3. 나머지 리스트에서 반복
- 1등이 판명되고 나면 2등석의 주인이 타이틀 방어전을 치룬다.
1라운드
2등석
|
list = [1, 4, 3, 5, 2, 7, 9]
|
1등석
- 1등석을 제외한 리스트에서 1등을 찾는 것으로 생각하면 편리하다.
2라운드
2등석
|
list_2 = [4, 3, 5, 2, 7, 9]
- 이 리스트를 가지고 1.의 과정을 반복한다.
2라운드
list[2]승
|
list_2 = [4, 3, 5, 2, 7, 9]
|
list[1]패
2라운드
list[3]패
|
list_2 = [4, 3, 5, 2, 7, 9]
|
list[2]승
2라운드
list[2]패
|
list_2 = [4, 3, 5, 2, 7, 9]
|
list[4]승
2라운드
list[5]패
|
list_2 = [4, 3, 5, 2, 7, 9]
|
list[4]승
2라운드
list[6]패
|
list_2 = [4, 3, 5, 2, 7, 9]
|
list[4]승
- 2라운드 최종 우승은 list[4]이다. list_2의 맨 앞의 값과 자리를 바꾸어준다.
2라운드
기존 2등석
|
list_2 = [2, 3, 5, 4, 7, 9]
|
2라운드 우승
- 원래의 리스트는 아래와 같이 된다.
2라운드
기존 2등석
|
list = [1, 2, 3, 5, 4, 7, 9]
|
2라운드 우승
이 과정을 리스트의 길이-1 라운드 만큼 반복하면 오름차순으로 정렬된 리스트가 나온다.
- 이와 같은 과정을 통해 정렬하는 것을 선택정렬(Selection sort)이라고 한다.
Python으로 구현하기
- 숫자의 리스트를 받으면 선택정렬 알고리즘을 통해서 오름차순으로 정렬해주는 함수를 만들어보자.
함수의 이름은 selection_sort로 하고 list_arg라는 매개변수를 통해 하나의 인자를 받도록 한다.
def selection_sort(list_arg):
- 리스트의 항목을 하나씩 순차적으로 다른 항목과 비교해야 하므로 for loop를 사용한다.
list의 길이와 같은 횟수 만큼 반복해야하므로 len(list_arg)로 리스트의 길이를 구하고 range 함수로 감싸서 0에서 리스트 길이까지의 시퀀스를 만들어준다.
루프에 사용될 시퀀스
range(len(list_arg)) = [0, 1, 2, 3, 4, 5, 6]
def selection_sort(list_arg):
for i in range(len(list_arg)):
def sort_list(arg):
for i in range(len(arg) - 1):
min_num = i
for j in range(i + 1, len(arg)):
if arg[min_num] > arg[j]:
min_num = j
arg[i], arg[min_num] = arg[min_num], arg[i]
print(arg)