선택 정렬

가장 작은 요소부터 선택해 맞는 위치로 옮기면서 순서대로 정렬하는 알고리즘

 

1. 주어진 배열의 요소들 중에서 최소값을 찾는다.

2. 해당 값을 배열의 맨 앞자리 요소와 교환한다.

3. 맨 앞자리를 뺀 나머지 요소들도 위와 같은 방법으로 교환한다.

 

즉, 정렬하지 않은 부분에서 최소값을 찾고,

그 값을 정렬하지 않은 부분의 첫 번째 요소와 교환하는 과정을 반복한다.

 

최소값을 찾으려고 비교한 횟수가 n-1, n-2, n-3, ... , 2, 1번이므로

시간 복잡도는 O(N^2)이다.

 

그리고 서로 떨어져 있는 요소를 교환하므로 안정적이지 않다.