🍀 선택 정렬(selection sort)

버블 정렬과 비슷하지만, 큰 값이 먼저 정렬되는 것과 달리 작은 값을 맨 앞으로 이동시키는 한 번의 swap만 일어나는 것이 특징이다. 선택 정렬의 naming에 맞게 작은 값을 선택하여 swap하는 방식으로 진행된다는 것이다. 아래 의사코드를 보면 선택정렬의 시간 복잡도는 O(N^2) 임을 알 수 있다. 버블정렬은 정렬이 되어있을 때 O(N) 시간 복잡도를 가지지만 선택 정렬에서는 정렬이 되어있는지 안 되어있는지 알 수가 없으므로 정렬의 유무와 상관없이 O(N^2) 의 시간 복잡도를 가진다. 아래 의사 코드는 오름차순 정렬 을 기반으로 작성했다.

Pseudo Code

• 1️⃣ for ⇒ i가 배열 길이 - 1까지
  • 2️⃣ for ⇒ j가 i + 1부터 배열 길이까지 돌면서 최소값 구하기
  • 3️⃣ 맨 앞의 index에 최소값을 swap

🌊 선택 정렬 시각화

그림이 너무 길어질 거 같아 포인트만 짚고자 2️⃣의 loop가 돌 때만을 기준으로 한다.

정렬 전 배열을 [5, 3, 4, 1, 2] 라고 하고 현재 최소값을 초록색, 비교할 값을 빨간색으로 표시한다.

조건: 현재 최소 값인(3) < 비교하는 값(4)
조건이 참이므로 최소 값 갱신이 일어나지 않는다.

조건: 현재 최소 값인(3) < 비교하는 값(1)
조건이 거짓이므로 최소 값 갱신이 일어난다. 1로 최소값 갱신

조건: 현재 최소 값(1) < 비교하는 값(2)
조건이 참이므로 최소 값 갱신이 일어나지 않는다.

조건: 현재 최소 값(1) < 비교하는 값(5)
조건이 참이므로 최소 값 갱신이 일어나지 않는다.

이제 2️⃣의 루프를 다 돌아 최소 값인 1을 찾았으니 맨 앞의 요소와 swap을 한다.

선택정렬에서 내부 루프는 위와 같이 동작하며 다음 동작은 아래와 같이 정렬이 될 것이다.

나머지 루프를 돌면서 같은 동작을 한다. 위의 예시에서는 이미 정렬이 끝나서 swap은 일어나지 않지만 루프는 끝까지 돈다.

위에서 루프는 끝까지 돈다 에 중요표시를 했는데 이는 "정렬은 다 되어 있을 때 버블정렬과 같이 정렬을 멈춰 시간 복잡도를 줄일 수 있는 방법은 없을까🤔?"라는 의문과 이어졌다.

⇒ 위와 같이 정렬이 동작하면 swap하여 정렬이 된 앞부분을 제외한 나머지 배열에서 정렬이 되었는지 안 되었는지를 알 수 있는 방법이 없다… 그래서 찾아보니 선택정렬 같은 경우는 정렬이되어 있는 경우에도 O(N^2) 의 시간 복잡도를 가진다는 것이 특징이다.

구현

이 구현에서 필요한 createArr, getCondition, swap 함수는 버블 정렬을 정리할 때 올린 곳에 있다. 따라서 위의 함수는 설명을 생략하고 구현부를 통으로 올렸다.

const createArr = (arrLength, maxNum) => {
  if (arrLength > maxNum) {
    throw Error("max number should be bigger than array length!");
  }

  const result = [];

  for (let i = 0; i < arrLength; i++) {
    let randomNum = Math.floor(Math.random() * maxNum);
    while (result.includes(randomNum)) {
      randomNum = Math.floor(Math.random() * maxNum);
    }
    result.push(randomNum);
  }

  return result;
};

const selectionSort = (arr, reverse = false) => {
  const getCondition = (num1, num2, reverse) => {
    return reverse ? num1 < num2 : num1 > num2;
  };

  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  const sortedArr = [...arr];
  for (let i = 0; i < arr.length - 1; i++) { // 👉🏻 1️⃣
    let maxOrMinIdx = i;
    for (let j = i + 1; j < arr.length; j++) { // 👉🏻 2️⃣
      if (getCondition(sortedArr[maxOrMinIdx], sortedArr[j], reverse)) {
        maxOrMinIdx = j;
      }
    }
    
 	// 👉🏻 3️⃣
    if (maxOrMinIdx !== i) swap(sortedArr, maxOrMinIdx, i);
    console.log("정렬 중... ", sortedArr, `\n${"=".repeat(30)}`);
  }

  return sortedArr;
};

const arr = createArr(5, 5);
console.log("선택정렬 전 👉🏻", arr);
console.log(`\n${"=".repeat(30)}`);
const sortedArrBySelectionSort = selectionSort(arr, (reverse = false));
console.log("\n선택정렬 후 👉🏻", sortedArrBySelectionSort);

테스트 결과 빨간색 박스를 배열의 맨 앞에서부터 점진적으로 정렬됨을 볼 수 있다.

reverse 테스트

...//
selectionSort(arr, (reverse = true));
...//

reverse도 잘 되었으니 선택 정렬에 대해서 정리해보자.

• 시간 복잡도
  - 정렬이 안 되어있을 때(최악) ⇒ O(N^2)
  - 정렬이 되어있을 때(최선) ⇒ O(N^2)
• 배열의 앞에서부터 점진적으로 정렬이 진행됨
• 추가적인 메모리 공간이 적게 필요함
• 퍼포먼스는 낮다.
• 교환 횟수가 적다.

🔥 마치며

전 시간에는 버블 정렬에 대해서 공부는데 이와 비교하면, 선택 정렬은 교환 횟수가 적게 정렬을 하고 싶은 상황을 제외하고는 큰 차이점을 찾지 못 했다. 다만, 정렬이 되어 있을 때를 고려하면 버블 정렬을 선택할 것이다. 하지만, 이 버블, 선택 정렬은 특정한 상황을 제외하고서 현실적으로 쓰기 어렵다고 한다. 🥲