CodeKata_Week 5_Day 1

📝 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;
}

🏆 Run Test!

🔎 알게된 것을 정리해보자!

✔ 정렬 알고리즘을 공부해야하는 이유는 효율적인 탐색을 위해서이다. 탐색해야하는 데이터가 정렬되어 있지 않다면 조회, 삽입, 삭제 등의 자료에 대한 접근 용이성이 떨어진다. 정렬 알고리즘은 무수하며 이는 시간 복잡도, 공간 복잡도를 해결하는데 목표를 둔다.