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

1. 개념

배열에서 최솟값을 찾아 해당번째 자리의 값과 교환을 모든 자리에서 시행하는 알고리즘.

2. Process

1. 주어진 배열에서 최소값의 index를 찾는다.

2. 첫번째 원소와 최소값의 위치를 교환

3. 첫번째 원소를 제외한 나머지 배열에서 같은 방법으로 교환.

 

3. GIF로 이해하기

http://algorithm.wiki/

4. 시간 복잡도와 공간 복잡도

시간 복잡도 : 최솟값 찾기 ( N ) * 모든 자리 ( N )

 O(n^2)

 

공간 복잡도 : 주어진 배열 안에서만 수행되므로

O(n)