코드카타 week 5_day 1

Selection Sort(선택정렬)

• 정렬 알고리즘: 순서가 없던 데이터를 순서대로 바꾸어 나열하는 알고리즘
• 대표적인 4가지: 선택정렬, 버블정렬, 삽입정렬, 퀵정렬
• 선택정렬: 정렬되지 않은 데이터 중 가장 작은 데이터를 선택해서 맨 앞에서부터 순서대로 정렬해 나가는 알고리즘
• It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.
  Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

예제) 배열 [7,5,4,2] 을 선택정렬로 정렬하기

• 첫 번째 loop: index 0부터 3까지 확인하며 가장 작은 수를 찾는다.
  👉 2 이므로 index 0의 7과 교체. -> [2,5,4,7]
• 두 번째 loop: index 1부터 3까지 확인하며 가장 작은 수를 찾는다.
  👉 4이므로 index 1의 5와 교체. -> [2,4,5,7]
• 세 번째 loop: index 2부터 3까지..

문제
nums라는 정렬되지 않은 숫자 배열을 주면, 오름차순(1,2,3..10) 으로 정렬된 배열을 return해주세요. (선택정렬 알고리즘으로 구현)

const selectionSort = (nums) => {
  // 아래 코드를 작성해주세요.
}

풀이

배열nums를 입력받았을 때

• 0번째 루프:
  • index 0부터 끝까지 확인하며 최솟값을 찾는다.
    최솟값 = Math.min(...nums)
  • 최솟값과 배열nums의 index 0의 값을 서로 바꾼다
    nums[nums.indexOf(최솟값)] = nums[0]
nums[0] = 최솟값
• 1번째 루프:
  • index 1부터 끝까지 확인하며 최솟값을 찾는다.
    최솟값 = Math.min(...nums.slice(1))
  • 최솟값과 배열nums의 index 1의 값을 서로 바꾼다
    nums[nums.indexOf(최솟값)] = nums[1]
nums[1] = 최솟값
• 2번째 루프:
  ...

따라서 반복되는 부분을 for문으로 간소화하면,

const selectionSort = (nums) => {
  for(let i=0; i<nums.length; i++){
    let num = Math.min(...nums.slice(i))   
    nums[nums.indexOf(num)] = nums[i]; 
    nums[i] = num; 
  }
  return nums
}

다른 풀이 By ChatGPT

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

배열의 두 요소를 서로 바꾸는 더 좋은 방법을 알게 됐다!
임의의 변수를 선언해서 돌려돌려 교체하는 방법 뿐이라고 생각했는데

let nums = [1,2,3]
let a = nums[0]
nums[0] = nums[2]
nums[2] = a

이렇게 배열 안의 배열을 쓰면 단 한줄로 처리할 수 있다

let nums = [1,2,3]
[nums[2], nums[0]] = [nums[0], nums[2]]