선택정렬 알고리즘 (Selection Sort)

• 배열에서 작은 값을 갖는 데이터를 선택하여, 앞으로 보내는정렬
• min 값을 찾아야하기 때문에 배열의 끝까지 탐색을 해야한다.

[ 5, 1, 2, 8, 7, 3, 9, 6, 10, 4 ]

위와 같은 배열이 존재 했을 때,

1. 먼저 index 0 부터 배열의 마지막 인덱스 까지 가장 적은 값(min)을 갖는 데이터를 찾는다.
2. min 값과 배열의 첫번째 인덱스와 swap을 한다.
3. 첫번째 인덱스는 가장 작은값이므로 두번째 인덱스부터 다시 탐색을 한다.
   
   ... 반복

[ 5 , 1 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 5 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 5 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 2 , 5 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ]

알고리즘 구현

from xmlrpc.client import MAXINT

def solution(array):
   answer = []
   min = MAXINT
   index = 0    
   
   for x in range(len(array)):
       min = MAXINT
       for y in range(x,len(array)):
           if min > array[y]:
               min,index = array[y],y
               
       
       array[x], array[index] = array[index], array[x]
   answer = array  
   return answer

시간 복잡도 O(N^2)

배열의 길이가 10일때,

1번째 min값을 찾기위해 10번 탐색

2번째 min값을 찾기위해 9번 탐색

...

10번째 min값을 찾기위해 1번 탐색

총 탐색 후 정렬 까지 10 + 9 + 8 + ... + 1 번 반복 되기때문에, 배열이 N일 경우,
= N * (N+1)/2
=> O(N^2)
해당 정렬은 O(N^2)의 시간 복잡도를 갖는다.

O(N^2)을 갖는 정렬

삽입정렬(Insertion Sort), 선택정렬(Selection Sort), 버블정렬(Buble Sort)가 존재한다.