Selection Sort(선택 정렬)

✨ 선택 정렬(Selection Sort)은 정렬되지 않은 데이터들에 대해
가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.

[ 10, 0, 97, -30, 5 ]

위 배열에 들어있는 숫자를 오름차순으로 정렬해보자.

Selection Sort 진행 과정

🎈선택 정렬 코드를 실행하면 위와 같은 과정으로 정렬이 진행된다.

가장 작은 값의 기준은 항상 맨 앞 index이다. 하지만, 정렬이 완료되는 순서도 가장 앞부터 완료된다.
이걸 고려했을 때, 가장 작은 값의 기준은 0, 1, 2, 3, ... 씩 증가한다고 생각하면 된다.

그렇게 나머지 오른쪽 값들과 반복 비교하여 가장 작은 값의 인덱스를 저장하고,
그 값이 첫 번째 기준값과 같은 것이 아니라면 서로 값을 교환해준다.

선택 정렬 수도 코드(Selection Sort Pseudo Code)

선택 정렬 최종 코드

🧨 위의 코드처럼 중첩 for loop을 이용하고, indexOfMin을 외부 for loop이 진행될 때마다 새로 설정해준다.
그리고 내부 for loop에서 반복 비교해주고, 가장 작은 값의 index를 얻어낸다.
최종적으로 처음에 초기화한 i인덱스와 같지 않은 지 확인하고, 같지 않다면 서로 값을 교환해준다.

if( indexOfMin !== i ) 조건문이 들어간 이유는, indexOfMin보다 작은 값을 찾지 못 했을 때
indexOfMin은 여전히 i값을 가지고 있을 것이기 때문에 그런 상황을 대비해주는 것이다.

버블 정렬과 비교했을 때, 여전히 시간 복잡도는 O(n^2)지만 이렇게 다른 방법으로 접근할 수도 있다.