[알고리즘] Selection Sort (선택정렬)

현재 위치에 들어갈 값을 찾아 정렬하는 방식
인간이 사용하는 정렬방식을 가장 많이 닮음

for i = 0 to n:
    a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
    a[i]와 a[j]의 값을 서로 맞바꾼다.

시간복잡도: O(n²)

장점
- 데이터 양이 적을 때 좋은 성능을 나타냄.
- 방법이 직관적임
- 비교는 여러번 수행되지만 실제 교환 횟수는 적다.
  (그럼으로 교환이 많이 이루어져야 하는 정렬에서 가장 효율적으로 적용된다.)
 
단점
- 데이터 양이 많아지면 속도가 현저히 떨어진다.
- 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 상황에서 최악의 처리 속도를 보여준다.

코드

[숫자의 정렬]

[문자의 정렬]

관련 영상