[알고리즘] JS - 선택 정렬(Selection Sort)

박기영·2022년 9월 20일

JavaScript 알고리즘 자바스크립트

알고리즘 및 자료구조

목록 보기

2/6

선택 정렬

가장 앞의 값을 기준으로 삼고, 배열 내에서 최소값을 찾는다.
최소값을 가장 앞의 값과 교환한다.
두 번째 값을 기준으로 삼고, 그 뒤의 배열에서 최소값을 찾는다.
최소값을 두 번째 값과 교환한다.
...

이렇게 반복되는 구조로 정렬이 진행되는 것을 선택 정렬(Selection Sort)라고 한다.

버블 정렬 때와는 반대로, n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해진다.

Big O

O(n^2) 의 시간복잡도를 지닌다.
또한, 이미 정렬되어 있는 배열을 탐색하더라도 O(n^2) 의 시간복잡도를 가진다.
매번 정해진 자리에 올 수 있는 최소값을 찾아야하기 때문이다.
따라서, 성능이 매우 떨어진다.

장점

in place 알고리즘이므로 메모리가 절약된다.

구현이 쉽다.

단점

Big O 부분에서도 언급되었듯이 성능 면에서는 효율이 좋지 않다.

Unstable

중복된 값의 데이터가 존재할 때, 두 데이터의 순서가 바뀔 수 있는 경우를 말한다.

참고 이미지

1이 최소값으로 잡혀서 왔기 때문에 중복된 5들 사이에서 순서 변화가 발생한 것을 확인할 수 있다.
이런 경우를 Unstable한 정렬이라고 한다.

구현 방법

function selectionSort(array) {
  // 배열의 첫 번째 인덱스부터 끝까지 반복한다.
  for (let i = 0; i < array.length; i++) {
    // i번째 인덱스가 최소값이라고 가정한다.
    let minIndex = i;

    // i번째 인덱스 뒤에 있는 모든 원소를 한번씩 순회한다.
    // 첫번째 for문에서, n번째 순회를 마치면 앞에서 n번째 데이터의 위치가 고정되기 때문이다.
    for (let j = i + 1; j < array.length; j++) {
      // 최소값이라고 가정한 i번째 인덱스 값이 j번 인덱스의 값보다 크다면
      if (array[minIndex] > array[j]) {
        // 최소값을 가진 인덱스를 j로 변경한다.
        minIndex = j;
      }
    }

    // 만약 minIndex의 값이 변경되었다면(두 번째 for문에서 연산이 진행됐다면)
    if (minIndex !== i) {
      // i번 인덱스의 값과 j번 인덱스의 값을 교환한다.
      let swap = array[minIndex];

      array[minIndex] = array[i];

      array[i] = swap;
    }

    console.log(`${i}회전: ${array}`);
  }

  return array;
}

console.log(selectionSort([5, 4, 3, 2, 1]));