16. 선택(Selection) 정렬 알고리즘

1. 개요

 선택 정렬은 버블 정렬과 마찬가지로 정렬중에서 가장 간단한 정렬이다. 두 정렬의 차이는 버블 정렬은 최대값을 찾아 맨 

뒤로 넣지만 선택 정렬은 최소값을 찾아 맨 앞으로 옮긴다. 언뜻보면 다른게 뭐냐고 말하는 사람들이 있겠지만 코드 내부의

차이로 버블 정렬은 안쪽 루프에 스왑 과정이 있고, 선택 정렬은 바깥 루프에 스왑 과정이 있어서 둘 다 O(n^2)이지만 

버블보다 선택 정렬이 조금 더 빠르다. 이 정렬들은 대규모 데이터가 아닌 속도에 크게 영향을 안받는 작은 데이터일 경우

사용된다. 정렬의 기초중의 기초이다.

2. 코드

2-1) 메인

2-2) 선택 정렬 알고리즘

2-3) 출력

3. 해설

 여러번 테스트를 거친 것은 아니지만 앞의 버블 정렬이 약 14초쯤 걸렸던 것에 비해서 선택 정렬은 약 12초가 걸렸다.

아주 미세하게 빠르며 코드 역시 간단하다. 혹시나 1000개 미만의 데이터를 정렬할 필요가 있을 경우 복잡한 퀵이나

머지 정렬보다 선택 정렬을 사용하는 게 낮다. (높이가 낮다, 알을 낳다, 오리 날다, 내가 낫다)

 기억해야할 것

 1) 최소값을 찾아 맨 앞으로 보낸다.

 2) 인덱스를 통해서 비교.