정렬 알고리즘 - 선택 정렬

선택 정렬(Seletion Sort)

• 요소들 중에서 최솟값을 찾아 맨 앞의 요소와 비교하여 정렬한다.
• 맨 앞을 제외한 요소들 중에서 다시 최솟값을 찾아 제외된 요소 다음의 위차와 비교 정렬 반복한다.
• 버블 정렬과 반대로 각 회전이 끝날 때마다 맨 앞의 데이터 위치가 정해진다.

시간복잡도

• O(n^2) : 선택 정렬은 매번 최솟값을 찾아야하므로 항상 시간복잡도가 동일하다.
  
  

장점

• 선택 정렬도 버블, 삽입 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있으며 알고리즘이 직관적이므로 이해하기도 쉽고 구현하기도 쉽다.
  
  

단점

• 선택 정렬은 최선의 경우와 최악의 경우 모두 O(n^2)의 시간이 걸리는 만큼 성능이 매우 떨어진다.
  
  

구현

'use strict';

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIdx] > arr[j]) {
        minIdx = j;
      }
    }

    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }

  return arr;
}

console.log(
  selectionSort([
    710, 509, 733, 224, 654, 154, 474, 166, 699, 102, 72, 272, 176, 450, 390,
    217, 928, 641, 210, 892,
  ])
);