[알고리즘] 선택 정렬

1. 선택 정렬이란

다음과 같은 순서를 반복하며 정렬하는 알고리즘

- 주어진 데이터중, 최소값을 찾음

- 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함

- 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

2. 어떻게 코드로 만들까?

데이터가 2개 일때(예: dataList = [9,1])

- data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_list[1] 값을 교환

 

데이터가 3개 일때(예: dataList = [9,1,7])

- 처음 한번 실행하면 1, 9, 7이 됨

- 두 번째 실행하면 1,7,9가 됨

 

데이터가 4개 일떄(예: dataList = [9,3,2,1])

- 처음 한번 실행하면 1,3,2,9가 됨

- 두번쨰 실행하면 1,2,3,9,가 됨

- 세 번쨰 실행하면, 변화 없음

 

3. 알고리즘 구현

- for stand in range(len(data) -1 )로 반복

- lowest = stand로 놓고

- for num in range(stand, len(data_list) stand 이후부터 반복

 - 내부 반복문 안에서 data_list[lowest] > data_list[num] 이면, lowest = num

- data_list[num], data_list[lowest] = data_list[lowest], data_list[num]

 

# 선택 정렬 함수
def Selection_sort(data_list):
    for stand in range(len(data_list)-1):
        lowest = stand
        for index in range(stand+1, len(data_list)):
            if data_list[index] < data_list[lowest] :
                lowest = index
        data_list[lowest], data_list[stand] = data_list[stand], data_list[lowest]
    return data_list
   
# 정렬 함수 정상작동 확인
import random
data_list = random.sample(range(100), 10)
print(data_list)
print (Selection_sort(data_list))

4. 알고리즘 분석

- 반복문이 두 개 O(n^2)

 - 실제로 상세하게 계산하면 n*(n-1) /2