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

* 선택정렬 (Selection Sort) 알고리즘 개념

 - 제자리 정렬(in-place sorting) 알고리즘의 하나.

 - 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘.

 - 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 최소값을 찾아 첫번째에 넣고, 두번째

  자료를 세번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중에서 가장 작은 최소값을 찾아 두번째 위치에 넣

  는 과정을 반복정렬하여 수행합니다.

 

 

 

* 선택정렬의 과정

 1. 주어진 배열중에 최소값을 넣습니다.

 2.  그 값을 맨 앞에 위치한 값과 교환합니다.

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

 4. 하나의 원소만 남을때까지 위의 1~3 과정을 반복합니다.

 

 

 

* 선택정렬 알고리즘의 장단점

 1) 장점

  - 자료 이동 횟수가 미리 결정됩니다.

  - 버블정렬과 다를게 없이 구현이 쉬운편에 속하는 정렬법입니다.

  - 비교횟수는 많지만 실제로 교환하는 횟수가 적기때문에 효율적입니다.

 2) 단점

  - 안정성을 만족하지 않습니다.

  - 값이 같은 숫자가 있는 경우에 상대적인 위치가 변경될 수 있습니다.

  - O(n^2)이라는 시간복잡도를 가지기 때문에 시간이 오래걸리는 정렬 방식입니다.

 

 

 

* 선택정렬 알고리즘의 샘플예제

 

 

 

* 선택정렬 파이썬코드

* 실행결과

 

 

 

* 선택정렬의 시간복잡도

 1) 비교 횟수

  - 두개의 for 루프의 실행횟수

  - 외부 루프 : (n-1)번

  - 내부 루프(최소값 찾기) : n-1, n-2, ...., 2, 1번

 

2) 빅오 표기법 

 

 

 

출처 1 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html