[Selection Sort]
1. 원리
1) 배열 A의 크기는 n
2) 배열 A[0...n-1]에서 가장 큰 값의 원소를 찾아 배열의 맨 끝인 n-1 번째 원소와 바꾼다.
3) 배열 A[0...n-2]에서 가장 큰 값의 원소를 찾아 n-2번째 원소와 바꾼다.
4) n-1번 반복
※Pseudo code
SelectionSort(A[], n) // 배열 A를 선택 정렬하는 함수 { for last <- n downto 2 // n에서 2까지 n-1번 for문 { A[FindMax(A, last)]<-> A[last]; // 배열 내 가장 큰 값과 끝 값 교환 } } |
FindMax(A[], last) // 배열 A[last]의 가장 큰 값의 인덱스 반환함수 { max <-1; // max 변수 첫번째 인덱스로 초기화 for i <- 2 to last // 2에서 현재 정렬되지 않은 배열의 끝까지 for문 { if ( A[i] > A[max] ) then max <- i; // 배열 내 가장 큰 값의 인덱스 찾기 } return max; // 배열 내 가장 큰 값의 인덱스 반환 } |
2. 수행시간
Θ(n^2)
- SelectionSort의 for문은 n-1번 순환
- 부분 배열 A에서 가장 큰 수를 찾는 FindMax의 for문은 부분 배열 크기에 비례 = (n-1)+(n-2)+(n-3)+...+2+1 = n(n-1)/2