[정렬] 선택정렬 (Selection Sort)

* 선택정렬 (Selection Sort)

  

 

- 선택을 해서 정렬하는 알고리즘

- 최소선택정렬 : 가장 작은 숫자를 선택(오름차순)

- 최대선택정렬 : 가장 큰 숫자를 선택(내림차순)

- 개선된 선택 정렬(기존의 선택정렬은 정렬하기 위한 배열이 하나 더 필요함)

- 최선, 최악의 경우가 따로 존재하지 않음

- 시간복잡도 O(n^2)

 

 

※ 오름차순 정렬에 대한 설명.

input = [15, 36, 26, 27, 2, 46]

 

- 정렬되지 않은 요소들의 맨 앞에 있는 요소를 minimum으로 설정한다. 

- 전체 요소들을 검사하면서 minimum(=15) 보다 작은지 비교한다.  

 

- minimum(=15) 보다 작은 숫자 2를 발견하게 되면 'minimum = 2' 로 만들어준다.

 

 

- 나머지 요소들을 계속 검사하면서 minimum(=2)보다 작은 숫자가 있는지를 확인한다.

- 만약 minimum(=2)보다 작은 경우 위에 처럼 minimum을 바꿔준다.

 

- 모든 요소들에 대해 위의 작업을 마친 후, 정렬되지 않은 요소들 중 맨 앞의 요소와 minimum(=2)의 위치를 서로 교환한다.

- 가장 작은 숫자인 2가 제일 앞에 정렬된다.

  

 

- 이제, 정렬된 숫자 2를 제외한 나머지 요소들에 대해 위의 작업을 반복해서 수행한다.

 

 

 

참고 사이트 : http://visualgo.net/

* 사이트를 통해 자세한 알고리즘 작동 방법을 확인할 수 있습니다.