[알고리즘] 선택 정렬(Selection Sort) [어떤 원소를 넣을지 선택하는 정렬 알고리즘]

---

- 선택 정렬(Selection Sort)이란?

1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째, …해서 (n－1) 번 반복한다. 어떻게 정렬이 되어 있든 일관성 있게 n(n－1)​／2에 비례하는 시간이 걸린다.
→ 인간이 사용하는 정렬 방식을 가장 많이 닮았다. (버블 정렬보다 두 배 정도 빠르다.)

선택 정렬 예시

선택 정렬(Selection Sort)의 예시 2

---

- 파생형 : 이중 선택 정렬(Double Selection Sort)

선택 정렬의 파생형으로, 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 최솟값은 1번째와 바꾸고 최댓값은 끝과 바꾼 다음 훑는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 방식 → 선택 정렬에 칵테일 정렬 방식을 도입

---