선택 정렬 (Selection Sort)

선택 정렬은 단계별로 최대값이나 최소값을 찾아서 배열의 뒤로 보내서 정렬하는 알고리즘 입니다.
이 때, 최대값을 뒤로 보낼 경우 오름차순 정렬, 최소값을 뒤로 보낼 경우 내림차순 정렬이 됩니다.

---

"4 5 3 6 7 2 1"인 배열을 선택 정렬로 오름차순 정렬해보겠습니다. 

---

최대값을 찾기 위해서 배열의 앞에서부터 배열을 탐색합니다.
일단 첫번째 요소인 4가 최대값이 됩니다. 
2번째 배열 요소인 5는 현재 최대값인 4보다 크므로 최대값을 5로 갱신합니다. 
3번째 요소인 3은 현재 최대값인 5보다 작으므로 다음 배열요소를 비교합니다.
이와 같은 방법으로 정렬되지 않은 배열의 마지막 요소까지 탐색, 비교하여 최대값을 찾으면 최대값은 7이되고 이를 정렬되지 않은 배열의 마지막 위치와 바꿔줍니다. (7과 1 교환)
그러면 마지막 그림과 같은 배열이 완성되고 7번째 요소는 정렬이 완료된 상태입니다

---

.

2단계에서도 마찬가지로 배열의 앞에서부터 정렬되지 않은 배열의 마지막 위치까지 탐색하여 최대값을 찾은뒤 정렬되지 않은 배열의 마지막 수와 교환해줍니다.
위의 예에서는 최대값인 6을 2와 교환하여 6번째 자리를 정렬 완료된 상태로 만들어줍니다.

---

---

---

---

---

배열의 첫 번째 요소까지 정렬을 완료하면 배열이 오름차순 정렬된 것을 확인할 수 있습니다.

---

시간 복잡도는 위의 예제를 보면 최대값을 구하기 위해서 단계별로 7, 6, 5, 4, 3, 2, 1 번 비교하는 것을 볼 수 있습니다. (배열 크기 n = 7)
배열의 크기를 n이라고 했을 때 연산 시간은  n + (n-1) + (n-2) + … + 1  = n*(n+1)/2 입니다.
따라서 시간 복잡도는 O(n2)이 됩니다.

---

소스코드 : https://gist.github.com/fpdjsns/4dd15fcb5d445577793686cf73fd6c28

선택 정렬(Selection sort).cc

실행결과