파이썬 선택 정렬 알고리즘(selection sort) 개념과 예제

파이썬 기초 과정이니 '알고리즘'이란 단어에 겁먹지 말자.

 

선택 정렬 알고리즘은 평소에 크기 순으로 물건이나 숫자를 정렬할 때 쓰는 사고 방식을 코드로 구현한 것이다.

한 반에서 키 순으로 자리를 선정할 경우를 생각해 보자.

 

 

네모=책상, 원=학생, 원 안에 숫자=키

우리가 키 순으로 설 때를 생각해보면 한 반에서 키가 제일 작은 아이가 맨 앞에 앉고,

두번째 자리부터 계속해서 자리에 앉지 않은 남은 아이들끼리 비교하여 제일 작은 아이가 순차적으로 자리에 앉는다.

이 논리를 그림으로 구현하면 다음과 같다.

 

선택 정렬 알고리즘 그림 예시

1세트에선 첫번째로 서있는 키 159인 학생과 나머지 185, 170, 162 학생들과 차례로 비교한다.

나머지 학생들 모두 159가 넘어서 159 학생은 제일 앞 책상(0번 인덱스)에 앉게 된다.

 

2세트에선 159를 제외한 나머지 학생들끼리의 비교를 통해 앞에서 두번째 책상(1번 인덱스)에 앉을 학생을 정한다.

159 학생 뒤에 있던 185 학생부터 다른 학생과 비교를 하게 되는데, 185 학생이 그 뒤에 있던 170 학생보다 크므로 자리순위에서 밀린다. 170 학생은 185 학생이 서있던 곳으로 가게 되고, 185 학생은 170 학생이 서있던 곳으로 간다. 이것을 맞교환이라 한다 (Swap)

그 다음, 170 학생과 162 학생을 비교하고, 162 학생이 더 작으므로 170 학생이 서있던 곳으로 가게 된다. (Swap)

더이상 비교할 학생이 없으니 162 학생이 두번째 책상(1번 인덱스)에 앉는다.

 

3세트에선 159, 162를 제외한 170, 185 학생끼리 비교하는데, 170 학생이 더 작으므로 170이 세번째 책상(2번 인덱스)에 앉는다.

 

마지막으로 185 학생 혼자 남아서 더이상 비교할 대상이 없으므로 185가 제일 뒤 책상(3번 인덱스)에 앉는다.

 

 

 

코드구현

---

위 자리 선정 예시에서 '맞교환' 개념을 강조하여 기술했다.

크기를 비교하여 큰 숫자가 작은 숫자 앞에 있으면 두 개의 숫자의 자리를 맞바꾸는 것을 말한다.

 

 

 

위 그림에서 첫 번째 원소를 i(기준변수), 나머지 원소를 j(비교변수) 라고 하고 오름차순 정렬할 때, i와 j를 차례로 비교하며 j가 i보다 작으면 j가 i자리로 가고 원래 i였던 숫자는 j 자리로 가게 된다.

 

정렬과정을 보면 제일 작은 숫자가 제일 왼쪽에 옮겨지는 것을 알 수 있다. 그래서 각 회차가 지날 때마다 i가 오른쪽으로 한 칸씩 이동한다.

위 그림으로 설명하면 1회차에서 i가 159였고, 2회차에선 i가 185로 되어 185 뒤에 나머지 숫자 j들과 비교한다. 

 

정렬할 대상의 원소를 n개라 했을 때, n-1번의 회차로 모든 원소가 정렬된다는 논리도 코드에 녹일 수 있을 것이다. 마지막에서 두번째 회차에서 정렬을 끝내면 마지막에 남은 숫자는 자연스레 제일 큰 숫자가 되기 때문에 마지막 숫자가 i가 되어도 비교할 j 가 없어서 생략한다.

 

 

 

 

선택 정렬 알고리즘을 코드로 구현하면 다음과 같다.

 

ls = [159, 182, 170, 162]
n = len(ls)
i,j = 0,0
print('정렬 전', ls)
for i in range(n-1):
    for j in range(i+1, n):
        if ls[i] > ls[j]:
            ls[i], ls[j] = ls[j], ls[i] # 맞교환
    print(ls)
print('정렬 후', ls)

>>>

정렬 전 [159, 182, 170, 162]
[159, 182, 170, 162]
[159, 162, 182, 170]
[159, 162, 170, 182]
정렬 후 [159, 162, 170, 182]

 

 

i 가 0번째부터 n-1번째까지 리스트 요소를 순회할 동안

중첩된 for문 속 j는 i 다음 인덱스부터 마지막 인덱스까지이기 때문에 i+1부터 n 까지 리스트 요소를 순회한다.

ls[i] 가 ls [j] 보다 클 때, 맞교환이 이루어지는 코드는 ls[i], ls[j] = ls[j], ls[i] 로 구현한다.

 

정렬 전과 정렬 후 사이 결과, 즉 for문 안의 출력 결과를 보면 맞교환 현황을 파악할 수 있다. 

 

 

 

내림차순 정렬은 ls[i]와 ls[j] 부분을 비교하는 코드 중 부등호 방향만 수정해주면 된다.

 

* 선택 정렬 내림차순 코드

ls = [159, 182, 170, 162]
n = len(ls)
i,j = 0,0
print('정렬 전', ls)
for i in range(n-1):
    for j in range(i+1, n):
        if ls[i] < ls[j]: # 이부분 수정
            ls[i], ls[j] = ls[j], ls[i] # 맞교환
    print(ls)
print('정렬 후', ls)

 

 

 

 

예제

---

 

* 코딩조건 *

- ls = [10,5,20,7,9,31,12,11,19,32] 를 이용하여 코딩

- 반드시 선택 정렬 알고리즘 활용하여 코딩

리스트 3개를 만들어서 홀수번째의 값, 짝수번째의 값을 따로 넣고

-짝수번째와 홀수번째의 차를 또다른 리스트에 넣어 출력하시오.

 

ls = [10,5,20,7,9,31,12,11,19,32]
odd=[0] * 5
even=[0] * 5
i, j=0,0
 
for i in range(len(odd)):
    for j in range(0,len(ls),2): # j -> 0,2,4,6,8
        if i==j-i:
            odd[i]=ls[j] # ls의 짝수번째 인덱스를 even[i]에 할당
            even[i]=ls[j+1] # j+1 -> 1,3,5,7,9 / ls의 홀수번째 인덱스를 odd[i]에 할당
 
eo=[i-j for i,j in zip(even, odd)] # 요소간 빼기 연산 
print("source :", ls)
print("odd :", odd)
print("even :", even)
print("e-o :", eo)

>>>

source : [10, 5, 20, 7, 9, 31, 12, 11, 19, 32]
odd : [10, 20, 9, 12, 19]
even : [5, 7, 31, 11, 32]
e-o : [-5, -13, 22, -1, 13]

 

 

선택 정렬 알고리즘의 ls[i], ls[j] = ls[j], ls[i] (맞교환) 코드를 이용하면

예제와 같이 어떤 리스트의 짝, 홀수번째의 요소들만 뽑아서 다른 리스트의 i번째 요소에 할당할 수 있다.

 

이 예제를 풀 땐 중첩 for문 속에서 비교 수식을 이용해 푸는 방법을 1시간 가량 고민했다.

i == j-i 수식을 이용하면,

0 == 0-0

1 == 2-1

2 == 4-2

...

 

 

이런식으로 반복되어서 odd와 even 리스트에 ls 리스트 요소를 할당하는 걸 한 번에 처리할 수 있다.