선택 정렬은 가장 간단한 정렬 알고리즘 중 하나입니다.
선택 정렬은 배열에서 가장 작은 값을 찾아 배열의 첫 번째 요소와 교체한 다음, 그 다음으로 작은 값을 찾아 배열의 두 번째 요소와 교체하는 정렬 방법입니다.
선택 정렬이 작동하는 방식은 다음과 같습니다.
- 배열에서 가장 작은 값을 찾습니다.
- 이 값을 배열의 첫 번째 요소와 교환합니다.
- 배열의 두 번째 요소에서 마지막 요소까지 위 과정을 반복합니다.
위의 과정을 배열의 크기만큼 반복하면 배열이 정렬됩니다.
선택 정렬의 시간 복잡도는 O(n^2)이며 불안정 정렬에 속합니다.
즉, 동일한 값을 가진 항목의 상대적인 위치는 정렬 후 유지되지 않을 수 있습니다.
또한 입력 배열이 이미 정렬되어 있어도 모든 요소를 비교하므로 비효율적입니다.