선택정렬의 이해

• selection sort
• 배열을 처음부터 끝까지 돌리면서, 현재 인덱스에 들어갈 값을 찾아 바꾸는 간단한 알고리즘
• 최소 선택 정렬, 최대 선택 정렬
• 오름차순, 내림차순
• O(n2)의 시간 복잡도와 O(n)의 공간 복잡도

참고 링크

방법1. for loop으로 구현

function get(str) {
  let arr = str.split(' ').map((n) => parseInt(n, 10));

  // 첫번 째 elem 은 i
  for (let i = 0; i < arr.length; i++) {
    // 첫번째 값을 최소값이라고 가정하고 저장
    let min = i;
    // 두번째 elem 은 j
    for (let j = i + 1; j < arr.length; j++) {
      // 만약 첫번째 elem > 두번째 elem 이면 최소값min 을 j로 업데이트
      if (arr[min] > arr[j]) {
        min = j;
      }
    }

    // 이제 최소값이랑 i랑 다르므로 두개의 위치를 swap 해줌
    if (i !== min) {
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }
  return arr;
}

console.log(get('4 23 8 5 7 41'));

방법2. map으로 구현

기본개념은 위와 같다. 단지 map으로 구현한 것만이 다른 점이다.

function get(str) {
  let arr = str.split(' ').map((n) => parseInt(n, 10));
  let len = arr.length;
  
  arr.map((elem, idx) => {
    let min = idx; // storing index of the minimum value

    for (let j = i + 1; j < len; j++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
    }
    
    if (i !== min) {
      // destruturing으로 순서를 바꿔준다.
      [arr[i], arr[min]] = [arr[min], arr[i]];
    }
  });
  return arr;
}

console.log(get('4 23 8 5 7 41'));