8장. 추가 연습 문제 : 선택 정렬 알고리즘

선택 정렬(Selection Sort)은 삽입 정렬, 거품 정렬과 더불어 기본적인 정렬 알고리즘이다.

 

선택 정렬 방법의 아이디어는 현재 범위에서 가장 작은 수를 선택하여 그 범위의 첫번째 위치로 선택한 수를 이동시키는 것이다. 단, 매 단계에서 범위를 1씩 줄여나간다. 즉, N개의 수로 이루어진 수열을 정렬하고자 할 때, 1단계는 첫번째 위치의 수~ N번째 위치의 수를 범위로 하고, 2단계는 두번째 위치의 수~N번째 위치의 수를 범위로 하고.....결국, 범위가 N번째 위치의 수~N번째 위치의 수가 되면 알고리즘은 종료된다.

 

예를 들어, 수열 7,4,1,8,2,5 을 오름차순으로 정렬하려고 한다. 이때, 각 단계의 선택 범위와 선택한 수의 이동 결과를 나타내면 다음과 같다.

 

1단계 범위 : 초기 수열의 첫번째 수~여섯번째 수
수열 7~5 중에 가장 작은 수 1을 '선택'하여, 7과 1을 비교한 후 교체한다.
1,4,7,8,2,5  => 이렇게 하면 1이 확정된다.

 

2단계 범위 : 1단계 수열의 두번째 수~여섯번째 수
이제 수열 4~5 중에 가장 작은 수 2를 '선택'하여, 4와 2를 비교한 후 교체한다.
1,2,7,8,4,5 => 이렇게 하면 2가 확정된다.

 

3단계 범위 : 2단계 수열의 세번째 수~여섯번째 수
이제 수열 7~5 중에 가장 작은 수 4를 '선택'하여, 7과 4를 비교한 후 교체한다.
1,2,4,8,7,5 => 이렇게 하면 4가 확정된다.

 

4단계 범위 : 3단계 수열의 네번째 수~여섯번째 수
이제 수열 8~5 중에 가장 작은 수 5를 '선택'하여, 8과 5를 비교한 후 교체한다.
1,2,4,5,7,8 => 이렇게 하면 4가 확정된다.

 

5단계 범위 : 4단계 수열의 다섯번째 수~여섯번째 수
이제 수열 7~8 중에 가장 작은 수 7를 '선택'하여, 7과 7를 비교한 후 교체한다.
1,2,4,5,7,8 => 이렇게 하면 7이 확정된다.

 

6단계 이제 8만 남아있으므로, 알고리즘은 종료된다.
1,2,4,5,7,8 => 정렬 끝

 

이러한 선택 정렬 알고리즘은 반복 구조과 재귀 구조를 이용하여 각각 구현해 보자.