선택 정렬 (Selection Sort) 은 정렬 알고리즘 중 한가지로, 구현이 굉장히 간단합니다.
선택정렬을 한문장으로 요약하면 "가장 작은 것을 계속 앞으로 보낸다" 입니다.
최솟값을 계속 왼쪽에 보내면서, 왼쪽은 정렬된 리스트, 오른쪽은 정렬되지 않은 리스트로 만듭니다.
빨간색은 정렬되지 않은 리스트의 최솟값, 파란색은 빨간색 요소와 교환될 요소 (혹은 교환 후 위치), 초록색은 이미 정렬된 리스트를 뜻합니다.
리스트 안에서 교환만을 이용해 추가 공간 필요 없이(교환 할 때 생기는 tmp는 제외) 정렬한다는 점에서 제자리 정렬로 볼 수 있습니다.