Selection Sort(선택 정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Selection Sort(선택 정렬)

선택 정렬은 제자리 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최솟값 or 최대값을 찾는다.

2. 그 값을 맨 앞 or 맨 뒤에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, 

n 개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n²) 만큼의 시간이 걸린다.

                     

출처 : 위키 백과

예제

[4, 54, 2, 8, 63, 7, 55, 56]    -> initial array

[4, 54, 2, 8, 56, 7, 55, 63]     -> after 1st swap

[4, 54, 2, 8, 55, 7, 56, 63]     -> after 2st swap

[4, 54, 2, 8, 7, 55, 56, 63]     -> after 3rd swap

[4, 7, 2, 8, 54, 55, 56, 63]     -> after 4th swap

[4, 2, 7, 8, 54, 55, 56, 63]     -> after 5th swap

[2, 4, 7, 8, 54, 55, 56, 63]     -> after 6th swap

의사 코드

Selection Sort(A[], n) {    // 배열 A[1...n]을 정렬한다.
for last <- n down to 2 {    ------------------------ ①
A[1...last] 중 가장 큰 수 A[K]를 찾는다;    ----- ②
A[k] <-> A[last];    ---------------------------- ③
}
}

실행 시간 : 

① 의 for 루프는 n-1 번 반복

② 에서 가장 큰 수를 찾기 위한 비교 횟수 : n-1, n-2, ... , 2, 1

③ 의 교환은 상수시간 작업

시간 복잡도

최선, 평균, 최악의 경우일 때에 선택 정렬에 소요되는 비교횟수를 C라고 했을때, 이를 수식으로 나타내면 다음과 같다.

수식에서 N은 테이블(또는 리스트)의 자료 수를 나타내며 는 평균, 는 최대, 는 최소를 나타낸다.

T(n) = (n-1) + (n-2) + ... + 2 + 1 =  Θ(n²)

소스 코드(Java)