선택 정렬(Selection Sort Algorithm)

선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬(Min-Selection Sort)과 최대 선택 정렬(Max-Selection Sort)로 구분 할 수 있다.

최소 선택 정렬은 오름차순으로 정렬될 것이고, 최대 선택 정렬은 내림차순으로 정렬될 것이다.

 

1. 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.

(정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것이다.)

2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.

3. 다음 인덱스에서 위 과정을 반복해준다.

 

이 정렬 알고리즘은 n-1개, n-2개... 1개씩 비교를 반복한다.

배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(N^2)이다.

 

공간복잡도는 단 하나의 배열에서만 진행하므로 O(N)이다.