Selection Sort

Loading...April 10, 2022

Concept

성능이 그리 좋지 않지만, 로직이 간단하여 인간이 하듯이 정렬한다.

insertion sort 보다 더 느리다. 그래서 List가 크다면 적절하진 않다.

버블 정렬보다 로직은 더 간단하더라도, 시간 복잡도는 같다.

How to work

  1. 제일 작은 숫자를 찾기 위해 순차적으로 이동
  2. Outer 루프가 한번 돌 때 마다 element 하나의 최종위치가 확정
  3. 탐색범위

    3-1. Outer: 0 -> n-1 (첫번째 element를 가장 낮은 숫자로 가정하고 시작)

    3-2. Inner: i+1 -> n-1 (이미 정렬 되어있는 부분 제외. 가장 낮은 숫자 다음 인덱스부터 비교하며 스왑)

Performance

Worst: O(n^2)

Average: O(n^2)

Best: O(n^2)

Source

function sortBySelection(arr) {
  let pos;
  for (var i = 0; i < arr.length; i++) {
    pos = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[pos]) {
        pos = j;
      }
    }
    const temp = arr[pos];
    arr[pos] = arr[i];
    arr[i] = temp;
  }
}

const arr = [4, 2, 6, 3, 9, 8, 5, 7];
sortBySelection(arr);
console.log(arr); // [2,3,4,5,6,7,8,9]