[JavaScript] 선택정렬

선택 정렬 (Selection Sort)

선택 정렬은 가장 작은 값을 선택해 배열의 맨 앞에 놓는 과정을 반복하며 배열을 정렬하는 간단한 알고리즘입니다.
"최솟값을 찾아서 제자리로 옮긴다"는 점에서 이름이 유래되었습니다.

---

동작 원리

1. 최솟값 찾기: 배열에서 아직 정렬되지 않은 부분의 최솟값을 찾습니다.
2. 교환: 찾은 최솟값을 현재 정렬 위치의 첫 요소와 교환합니다.
3. 반복: 배열이 정렬될 때까지 1~2 단계를 반복합니다.

---

장단점

• 장점: 구현이 매우 쉽다. 데이터 이동 횟수가 적어, 교환이 적은 환경에 적합하다.
• 단점: 시간 복잡도가 비효율적이다 (O(n2)O(n^2)O(n2)).
• 적합한 경우: 데이터 양이 적거나 교환 비용이 높은 경우.

---

예시 코드 (JavaScript로 구현)

1. 오름차순 선택 정렬

const selectionSort = (array) => {
  const arr = array.slice(); // 원본 배열 복사
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i; // 최솟값의 인덱스 초기화

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j; // 최솟값의 인덱스 갱신
      }
    }

    // 최솟값과 현재 위치를 교환
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
};

const an = [5, 1, 4, 2, 8];
console.log(selectionSort(an)); // [1, 2, 4, 5, 8]

 

2. 내림차순 선택 정렬

const selectionSortDesc = (array) => {
  const arr = array.slice();
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let maxIndex = i; // 최댓값의 인덱스 초기화

    for (let j = i + 1; j < n; j++) {
      if (arr[j] > arr[maxIndex]) {
        maxIndex = j; // 최댓값의 인덱스 갱신
      }
    }

    // 최댓값과 현재 위치를 교환
    if (maxIndex !== i) {
      [arr[i], arr[maxIndex]] = [arr[maxIndex], arr[i]];
    }
  }

  return arr;
};

const an = [5, 1, 4, 2, 8];
console.log(selectionSortDesc(an)); // [8, 5, 4, 2, 1]

 

선택 정렬 동작 예시

배열: [5, 1, 4, 2, 8] (오름차순 정렬)

1단계:

• 최솟값 찾기: 배열 [5, 1, 4, 2, 8]에서 1
• 교환: 1 ↔ 5 → [1, 5, 4, 2, 8]

2단계:

• 최솟값 찾기: 배열 [5, 4, 2, 8]에서 2
• 교환: 2 ↔ 5 → [1, 2, 4, 5, 8]

3단계:

• 최솟값 찾기: 배열 [4, 5, 8]에서 4
• 교환: 그대로 → [1, 2, 4, 5, 8]

4단계:

• 최솟값 찾기: 배열 [5, 8]에서 5
• 교환: 그대로 → [1, 2, 4, 5, 8]

---

시간 복잡도

• 최선, 최악, 평균 모두: O(n2)O(n^2)O(n2)
  • 항상 nnn번의 비교가 필요하기 때문.