Udemy - 선택 정렬

---

선택정렬이란?

선택정렬은, 버블정렬과 반대로 가장 작은 값을 찾아서 배열의 제일 앞에 쌓는 방식을 사용한다.
따라서 버블정렬과 알고리즘 메카니즘 자체는 굉장히 비슷하다고 볼 수 있다.

위와 같이 배열의 가장 첫 요소부터 검사를 시작하며, 해당 값보다 작은값이 있는지 계속 체크한다.

기준 값보다 작은 값을 발견하면, 버블 정렬처럼 바로 Swap을 해주는 것이 아니라 포인터를 그 값으로 우선 이동시킨다. 그리고 해당 포인터의 값을 기준으로 다시 남은 끝부분까지 검사를 반복하며 배열에서 “가장 작은 값”을 찾아내어 제일 앞으로 이동시키는 것이다. 따라서 선택 정렬의 핵심은 가장 작은 값을 찾아서 앞으로 옮겨주는 것이라고 할 수 있다.

---

선택정렬 기본 예제

주어진 배열을 선택 정렬 방식으로 정렬하는 알고리즘을 작성하시오.

function selection(arr) {
  // i는 배열의 시작점을, tempMin은 계속 변경될 최소값을, j는 비교를 위한 포인터를 의미한다.
  let i = 0;
  let tempMin = i;
  let j = tempMin + 1;
  while (i < arr.length - 1) {
    if (j > arr.length - 1) {
      [arr[i], arr[tempMin]] = [arr[tempMin], arr[i]];
      i++;
      tempMin = i;
      j = tempMin + 1;
    }
    if (arr[tempMin] > arr[j]) {
      tempMin = j;
      j++;
      continue;
    }
    j++;
  }
  return arr;
}

selection([22, 10, 3, 14, 30, 14]);

---

선택 정렬의 시간 복잡도

$O(n^2)$ 의 시간복잡도를 갖는다.
이 또한 그리 효율적이지는 않은 알고리즘이지만, 그래도 swap을 버블정렬보다는 덜 하기 때문에 조금 더 나은 선택이 될 수는 있다.

---