[알고리즘] 선택정렬

[Selection Sort]

• 주어진 리스트 중에 최솟값을 찾아, 그 값 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정리하는 알고리즘
• 매번 가장 작은 것을 선택한다 라는 의미에서 선택정렬 알고리즘이라고 한다.
• N-1 만큼 최솟값을 찾아 맨 앞으로 보내야 한다. 
  따라서 연산 횟수는 \( N + (N-1) + (N-2) +(N-3) + ... + 2 = (N-1)(N+2)/2 = O(N^2)  \)

---

과정 )

가장 작은 숫자인 1을 가장 앞에 있는 숫자인 4와 자리를 바꾸고, 

그다음 가장 작은 숫자인 2는 정렬이 잘 되어 있고,

그다음 작은 숫자인 3을 3번째 위치에 있는 5와 바꾸고...

---

def select_sort(datas):
    for i in range(len(datas)-1):
        min_index = i
        for j in range(1+i,len(datas)):
            if datas[j] < datas[min_index]:
                min_index = j
        datas[i],datas[min_index] = datas[min_index],datas[i]

datas = [4,2,5,1,3]
select_sort(datas)
print(datas)

i를 임의로 min이라 저장한다.

이후 나머지 부분들을 j가 돌면서 min보다 더 작은, 최솟값이 있는지 찾아낸다. ( range( 1+i , len(datas) ) 만큼 돈다. )

 

첫 for문이 다 돌고 마지막에 가면 위 그림과 같은 상태가 된다.

i를 min이라 저장하고, j와 비교하여 j가 더 작다면 i와 위치를 바꾼다.

 

보다시피 마지막 비교는 인덱스 len(datas) - 2 에서 끝나므로,

range( len(datas) -1 ) 인 것이다.

 

안의 for 문의 경우,

인덱스 1+i 부터 마지막 요소까지 다 돌아야 하므로

range( 1+i , len(datas) ) 가 된다.

---

[실습1] 선택 정렬 알고리즘을 이용해 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 프로그램을 만들어보자.

import random
import copy
def select_sorted(datas, ASC = True):
    cdatas = copy.deepcopy(datas)
    if ASC:
        for i in range(len(cdatas)-1):
            min_idx = i
            for j in range(1+i,len(cdatas)):
                if cdatas[j]<cdatas[min_idx] :
                    min_idx = j
            cdatas[min_idx],cdatas[i] = cdatas[i],cdatas[min_idx]
    else :
        for i in range(len(cdatas)-1):
            max_idx = i
            for j in range(1+i,len(cdatas)):
                if cdatas[j]>cdatas[max_idx] :
                    max_idx = j
            cdatas[max_idx],cdatas[i] = cdatas[i],cdatas[max_idx]
    return cdatas


scorelist = [random.choice(range(0,101)) for _ in range(20)]
print(f'오름차순 : \n{select_sorted(scorelist,ASC=True)}')
print(f'내림차순 : \n{select_sorted(scorelist,ASC=False)}')
print(f'원본 데이터 : \n{scorelist}')

'''
오름차순 : 
[0, 0, 1, 4, 7, 8, 10, 42, 51, 52, 58, 72, 75, 76, 79, 79, 79, 83, 87, 98]
내림차순 :
[98, 87, 83, 79, 79, 79, 76, 75, 72, 58, 52, 51, 42, 10, 8, 7, 4, 1, 0, 0]
원본 데이터 :
[4, 83, 79, 52, 7, 42, 8, 10, 58, 87, 79, 0, 0, 76, 72, 51, 1, 79, 98, 75]
'''