[알고리즘] 선택정렬 Selection Sort

다양한 정렬 알고리즘 중, 선택 정렬에 대해 알아보자.

 

선택 정렬은 말 그대로 선택을 해서 정렬하기 때문에 "선택 정렬 " 이라고 생각하면 되는데,

 

배열의 원소를 탐색하다가 가장 큰 수를 가장 뒤에 정렬 하도록 한다.

 

 

pseudo code는 다음과 같다.

 

 

selectionSort(A[], n) -> 배열 A[1,,n]을 정렬한다

{

       for last <- n downto 2  {

            A[1...last] 중 가장 큰 수 A[k]를 찾는다;

            A[k] <-> A[last];    => A[k]와 A[last] 값을 교환

      }

}

 

 

시간 복잡도는 O(n^2) 에 해당한다.