선택 정렬

배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

실행 시간의 상한 : O(n^2)

실행 시간의 하한 : Ω(n^2)

실행 시간의 상한, 하한 모두 버블 정렬과 동일하다.