CodeKata_Week 5_Day 1

Jisun Lee·2021년 8월 22일

📝 Today Question

Selection Sort(선택정렬): 선택정렬은 정렬되지 않은 데이터 중 가장 작은 데이터를 선택해서 맨 앞에서부터 순서대로 정렬해 나가는 알고리즘입니다. 선택 정렬 알고리즘을 사용하여 문제를 풀어보세요.

✏️ Problem Statement
nums라는 정렬되지 않은 숫자 배열을 주면, 오름차순(1,2,3..10) 으로 정렬된 배열을 return해주세요.

🔎 선택 정렬이란 무엇일까?

출처: https://velog.io/@roro/자료구조알고리즘-선택정렬

✔ Check Point 1
: 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

✔ Check Point 2
: 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 n회전에서는 n번째 자료를 정렬한다.

✔ Check Point 3
: 장점-자료 이동 횟수가 미리 결정된다.
: 단점-같은 값이 있는 경우 상대적인 위치가 변경될 수 있기 때문에 안정성이 만족되지 않는다.

출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

🔎 문제를 어떻게 접근해야할까?

🏃

const selectionSort = (nums) => {
  for (let i = 0; i<nums.length; i ++) {
    let min = i;
    for (let j = i+1; j<nums.length; j++){
      if (nums[min]>nums[j]){
        min = j;
      }
    }
    if (min!==i){
      let change = nums[min];
      nums[min] = nums [i];
      nums[i] = change;
    }
  }
  return nums;
}