정렬 알고리즘 - 선택 정렬

선택 정렬은 버블 정렬과 유사하지만, 배열을 순회하면서 가장 작은 값을 찾고 그 값의 위치를 교환하면서 정렬하는 방식이다.

const arr = [7, 20, 1, 51, 32, 55, 126] // 시작값

위 배열에서 우선 최초 값으로 20을 설정한다. 그리고 배열을 순회하면서 가장 작은 값인 1을 첫 번째 자리와 위치를 교환한다.

[1, 20, 7, 51, 32, 55, 126] // 1회차

그리고 다음은 2번째 자리부터 가장 작은 값을 찾고, 또 찾은 가장 작은 수와 위치를 교환한다. 이 과정을 배열을 끝까지 순회할 때까지 반복한다.

[1, 7, 20, 32, 51, 55, 126] // 결과

/**
 * @param {number[]} arr
 * @returns number[]
 */
const selectionSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j;
      }
    }
    if (i !== lowest) {
      let temp = arr[i];
      arr[i] = arr[lowest];
      arr[lowest] = temp;
    }
  }

  return arr;
};

console.log(selectionSort([7, 20, 1, 51, 32, 55, 126, 13])); // [1, 7, 20, 32, 51, 55, 126]

코드로 작성해 보면 다음과 같다.

1. 첫 번째 값을 최솟값(i: 최솟값의 인덱스)으로 설정한다.
2. 최솟값의 다음 요소부터 작은 값이 있는지를 체크하고 루프가 끝날 때 선택된 값과 최솟값의 위치를 바꾼다.
3. 정렬된 최솟값의 다음 값을 다시 최솟값으로 설정한다.
4. 모든 요소를 순회할 때까지 반복한다.

선택 정렬 알고리즘은 모든 요소들을 검사해야하기 때문에, 그리 시간복잡도가 좋지 않다. 최악의 경우, O(n²)이 나온다.