Programming/Algorithm

선택 정렬 (Selection Sort)

자강 2018. 9. 1. 02:18

[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