algorithm

자바스크립트로 선택정렬 구현(selection sort in javascript)

선택정렬

선택정렬은 이름에서 알 수 있듯이 정렬되지 않은 배열 중에 현재 위치에 맞는 값을 선택해서 위치를 교환하는 알고리즘이다. 버블정렬, 삽입정렬과 같은 비교 알고리즘 중 하나이므로 O(N2)의 시간복잡도를 가지고 있다. 선택정렬은 정렬 알고리즘으로서 좋은 퍼포먼스는 보여주지 못하지만, 구현하기 쉽고 이해하기 쉽다는 장점을 가지고 있다.

자바스크립트로 구현

function selectionSort(arr = []) {
// copy array
let result = [...arr];

for (let i = 0; i < result.length - 1; i++) {
  // 현재 인덱스를 최소값이라고 가정한다.
  let minimunNumberPos = i;

  // 오직 정렬되지 않은 배열에서만 탐색하기 위해서 j를 i + 1로 설정한다.
  for (let j = i + 1; j < result.length; j++) {
    if (result[minimunNumberPos] > result[j]) {
      minimunNumberPos = j;
    }
  }

  // swap
  if (minimunNumberPos !== i) {
    let temp = result[minimunNumberPos];
    result[minimunNumberPos] = result[i];
    result[i] = temp;
  }
}

return result;
}

console.log(selectionSort([2, 1, 4, 3, 5])); // [1,2,3,4,5]
console.log(selectionSort([710, 509, 733, 224, 654, 154, 474, 166, 699, 102, 72, 272, 176, 450, 390, 217, 928, 641, 210, 892]));
// [86, 111, 190, 220, 385, 445, 458, 516, 517, 527, 604, 608, 611, 614, 831, 876, 893, 913, 949, 970]