Time and Space Complexity

시간 복잡도:

• 최선, 평균, 최악의 경우: O(n²)
  • Selection Sort는 배열이 이미 정렬되어 있더라도 항상 정렬되지 않은 부분 전체를 스캔하여 최솟값을 찾습니다. 비교 횟수는 입력 순서에 의존하지 않습니다.

공간 복잡도:

• O(1)
  • Selection Sort는 "in-place" 알고리즘입니다. 입력 크기에 상관없이 일정한 양의 추가 메모리만을 사용하여 요소를 재배치합니다.

요약:

• Selection Sort는 단순하고 메모리 효율적입니다.
• 교환 횟수가 적으며(최대 n-1번), 이는 쓰기 작업 비용이 많이 드는 경우에 유용합니다.
• 2차 시간 복잡도(quadratic time)로 인해 대규모 데이터 세트에는 적합하지 않으며, Merge Sort나 Quick Sort와 같은 알고리즘이 선호됩니다.