📋 선택 정렬 알고리즘

선택 정렬은 루프를 돌며 가장 작은 것을 선택해서 앞으로 보내는 정렬방법이다.

저번에 살펴본 버블 정렬과는 가장 작은 것을 선택한다는 부분이 확실히 다르다.
사실 말보다는 작동방식을 직접 눈으로 보는게 이해가 빠를 것이다. 한번 살펴보자.

---

📌 1. 선택 정렬 작동 방식

https://visualgo.net/en/sorting

루프를 돌며 가장 작은값을 저장한 뒤, 현재 인덱스와 저장된 가장 작은 값을 교환한다.

---

📌 2. 선택 정렬 구현

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j;
      }
    }
    console.log(i, lowest);
    let temp = arr[i]
    arr[i] = arr[lowest]
    arr[lowest] = temp;
  }
  return arr;
}

selectionSort([0, 2, 34, 22, 10, 19, 17])

내게 가장 익숙한 자바스크립트로 작성했다.

이 방식은 분명 제대로 작동한다. 하지만 중간에 찍은 console.log 내용을 한번 살펴보자.

i lowest
 0 0
 1 1
 2 4
 3 6
 4 5
 5 6
 6 6

살펴보면 i와 lowest가 같은 상황에서도 이 로직은 쓸데없이 스왑을 한다.

이를 방지하려면 어떻게 해야할까? 나는 스왑이 실행되기 전, if문으로 제약을 걸어줬다.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
      let lowest = i;
      for (var j = i + 1; j < arr.length; j++) {
          if (arr[j] < arr[lowest]) {
              lowest = j;
          }
      }
      if (i !== lowest) {
          console.log(i, lowest);
          let temp = arr[i]
          arr[i] = arr[lowest]
          arr[lowest] = temp;
      }
  }
  return arr;
}

selectionSort([0, 2, 34, 22, 10, 19, 17])

이제 다시 console을 살펴보면 값은 이러하다.

i lowest
 2 4
 3 6
 4 5
 5 6

이제 쓸데없는 스왑을 하지 않고 4번만 실행되는 것을 알 수 있다.

---

📌 3. 선택 정렬의 시간 복잡도

O(n^2) 이다.
배열 길이가 길어지면 비교 횟수도 n에 n을 곱한, n^2 비율로 늘어난다.

선택 정렬이 잠재적으로 버블 정렬보다 나은 시나리오는 단 하나인데, 어떤 이유나 상황으로 스왑 수를 최소화하는 경우이다.

버블 정렬을 상기해보면 기본적으로 가장 큰 항목을 끝까지 가져갈 수 있도록 계속 스왑한다.

하지만 선택 정렬에서는 반복하여 많이 비교하지만, 각 루프가 끝날 때 한 번만 바꾼다. 때문에 이런 경우에선 선택정렬이 더 나은 선택이 될 수 있다.