선택 정렬(Selection Sort)

시간복잡도

n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다

그림 설명

선택 정렬

---

1. 첫번째 for문을 통해 초기 인덱스 번호를 idx에 저장
2. 두번째 for문을 통해 그 다음 인덱스를 확인하며 idx에 저장된 수보다 작은 경우 해당 idx 번호를 idx에 저장
   (idx에는 가장 작은 수의 인덱스 번호가 저장됨)
3. 저장된 idx 숫자와 초기 for문에서 설정된 idx 숫자와 자리를 바꿔준다.
4. 해당 과정을 반복할 시 오름차순으로 숫자가 정렬된다.

function solution(arr) {
  let answer = arr;

  for ( let i = 0; i < arr.length - 1; i++ ) {
    // 초기 인덱스 번호 idx에 저장
    let idx = i;
    for ( let j = i+1; j < arr.length; j++ ) {
      // arr[idx] 보다 작은 값 나타나면 그 인덱스를 idx로 바꿔줌
      if (arr[j] < arr[idx]) idx = j;
    }
    // 각 배열을 교환
    [arr[i], arr[idx]] = [arr[idx], arr[i]];
  }

  return answer;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr))

---

장점

• Bubble sort와 마찬가지로 알고리즘이 단순하다.

• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.

• Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

단점

• 시간복잡도가 O(n^2)으로, 비효율적이다.

• 불안정 정렬(Unstable Sort) 이다.

Conclusion

Bubble Sort와 유사하지만, 조금 더 빠른 Selection Sort에 대해 알아봤다. 기술 면접이나 시험(n번째 회전에 정렬 상태)에서도 종종 나오는 정렬이니 알아두면 좋다.

---

참조
https://gyoogle.dev/blog/algorithm/Selection%20Sort.html