Selection Sort에 대해 설명해보세요.

---

Selection Sort의 작동 방식

• Selection Sort는 매 차례 최솟값을 선택하여 앞으로 보내면서 정렬하는 방식의 알고리즘이다.

• 차례가 끝나면 선택된 원소는 다음 차례에서 선택할 때 제외된다.

---

Selection Sort의 특징

• 시간 복잡도
  : 크기가 N인 배열의 경우, 매 차례 최솟값을 찾는 비교 횟수는 (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2이므로 O(N^2)의 시간 복잡도를 가진다.

• 공간 복잡도
  : 배열 안에서 교환이 진행되므로 다른 메모리 공간이 필요없이 O(N)의 공간 복잡도를 가진다.

• 장점

  • 구현이 간단하여 단순성이 높다.
  • Bubble Sort에 비해 실제로 교환되는 횟수가 적어 조금 더 빠르다.

• 단점

  • 단순성에 비해 효율성이 떨어진다.

---

결론

Selection Sort는 최솟값을 선택하여 앞에서부터 정렬시키는 알고리즘입니다. 시간 복잡도는 최솟값을 찾는 과정에서 O(N^2)를 가지며, 공간 복잡도는 배열의 크기만큼인 O(N)을 가집니다. 구현이 단순하지만 그 만큼 효율성이 떨어지므로 데이터 수가 적은 경우 사용하는 것이 유리합니다.