선택정렬(Selection Sort)

발췌 : [IT COOKBOOK] C·C++로 배우는 자료구조론 p353

---

선택정렬은 가장 큰 것을 선택하여 가장 마지막 것과 스와핑하는 방식입니다.

선택정렬은 이름 그대로 선택하여 정렬하는 방법입니다. 가장 큰 수를 선택하기 위해서 정렬되지 않는 수의 나열을 모두 검사하고, 선택된 수를 정렬되지 않은 수의 나열의 가장 오른쪽의 수와 스왑(Swap)합니다.

<선택정렬 순서>
 ㅇ아래와 같은 수의 나열이 있을 경우 선택정렬을 사용 할 때의 모양을 알아보겠습니다.

1. 22부터 12까지의 수의 나열을 모두 검사하여 가장 큰 수인 37을 선택합니다.

2. 선택된 가장 큰 수인 37을 정렬되지 않은 수의 나열의 가장 오른쪽에 있는 12와 스왑합니다.

3. 22부터 19까지의 수의 나열을 모두 검사하여 가장 큰 수인 22를 선택합니다.

4. 선택된 가장 큰 수인 22을 정렬되지 않은 수의 나열의 가장 오른쪽에 있는 19와 스왑합니다.

5. 19부터 15까지의 수의 나열을 모두 검사하여 가장 큰 수인 19를 선택합니다.

6. 선택된 가장 큰 수인 19을 정렬되지 않은 수의 나열의 가장 오른쪽에 있는 15와 스왑합니다

7. 15부터 12까지의 수의 나열을 모두 검사하여 가장 큰 수인 15를 선택합니다.

8. 선택된 가장 큰 수인 15을 정렬되지 않은 수의 나열의 가장 오른쪽에 있는 12와 스왑합니다

 Tip
선택정렬은 N²의 효율이기 때문에 사실상 매우 느린 정렬입니다. 그래서 데이터의 양(개수)가 많아지면 효율이 나빠지게 됩니다. 하지만 비교횟수가 O(N²)인 반면, 데이터의 스왑(swap)은 O(N)입니다. 그래서 데이터 용량(크기)이 클 때 사용 할 경우 유리 합니다.

 연한 녹색으로 칠해진 숫자의 나열은 '정렬되지 않은 숫자의 나열'이고, 진한 녹색으로 칠해진 숫자의 나열은 '정렬된 수의 나열'입니다.
(앞으로는 언급하지 않겠습니다.)