Selection Sort (선택 정렬)

선택 정렬은 제자리 정렬^[각주:1] 알고리즘의 하나로, 아래와 같이 실행된다.

1. 주어진 리스트 중 최소값을 찾는다.

2. 최소값과 시작점의 값을 교체한다.

3. 시작점을 제외한 나머지 리스트를 같은 방법으로 교체한다.

예를 들자면 arr[] = {64, 25, 12, 22, 11}의 값을 가지고 있는 배열의 선택정렬 실행순서는 아래와 같다.

1. 위 배열의 가장 작은 값은 11 이다. 11과 64(시작점)의 자리를 교체한다. - 11 25 12 22 64

2. 정렬된 11을 제외한 값 중 가장 작은 값은 12 이다. 25(시작점)와 12의 자리를 교체한다. - 11 12 25 22 64

3. 정렬된 11, 12를 제외한 값 중 가장 작은 값은 22 이다. 25(시작점)와 22의 자리를 교체한다. - 11 12 22 25 64

4. 정렬된 11, 12, 22를 제외한 값 중 가장 작은 값은 25 이다. 25의 자리는 변경없다. (시작점이므로) - 11 12 22 25 64

선택 정렬의 시간 복잡도는 O(n*n)이고, 코드는 아래와 같다. (Java Code)

1. 제자리 정렬은 원소들의 갯수에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘 [본문으로]