μ½”λ”© ν…ŒμŠ€νŠΈ/μ•Œκ³ λ¦¬μ¦˜

JavaScript둜 μ•Œμ•„λ³΄λŠ” 선택 μ •λ ¬(Selection Sort)κ³Ό 예제 μ½”λ“œ

μš©λ‡½ 2023. 10. 12. 17:14
λ°˜μ‘ν˜•

μ†Œκ°œ

μ£Όμ–΄μ§„ λ¦¬μŠ€νŠΈμ—μ„œ κ°€μž₯ μž‘μ€ 값을 μ„ νƒν•˜μ—¬ 맨 μ•žμ— μœ„μΉ˜μ‹œν‚€κ³ , κ·Έλ‹€μŒμœΌλ‘œ μž‘μ€ 값을 μ°Ύμ•„ 두 번째 μœ„μΉ˜μ— μœ„μΉ˜μ‹œν‚€λŠ” 과정을 λ°˜λ³΅ν•˜μ—¬ μ •λ ¬ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€.

μ•žμœΌλ‘œ 보내진 μ›μ†ŒλŠ” 더 이상 μœ„μΉ˜κ°€ λ³€κ²½λ˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

κΈ°λ³Έ κ°œλ…

선택 정렬은 κ°„λ‹¨ν•˜λ©΄μ„œλ„ μ΄ν•΄ν•˜κΈ° 쉽고 μ½”λ“œ κ΅¬ν˜„μ΄ μ‰¬μš΄ μ•Œκ³ λ¦¬μ¦˜μ΄μ§€λ§Œ, 그만큼 μ‹œκ°„ λ³΅μž‘λ„κ°€ λ†’μ•„ λŒ€κ·œλͺ¨ 데이터λ₯Ό μ •λ ¬ν•  λ•ŒλŠ” μ„±λŠ₯이 λ–¨μ–΄μ§€λŠ” 단점이 μžˆμŠ΅λ‹ˆλ‹€.

선택 μ •λ ¬μ˜ μ‹œκ°„ λ³΅μž‘λ„λŠ” O(N^2)으둜, μž…λ ₯ λ°μ΄ν„°μ˜ 크기가 컀질수둝 μ„±λŠ₯ μ €ν•˜κ°€ λ”μš± μ‹¬ν•΄μ§‘λ‹ˆλ‹€.

예제 μ½”λ“œ

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArr = [3, 1, 6, 2, 9, 0];
const sortedArr = selectionSort(unsortedArr);
console.log(sortedArr); // [0, 1, 2, 3, 6, 9]
  1. λ°°μ—΄μ˜ 길이λ₯Ό λ³€μˆ˜ n에 μ €μž₯ν•œ λ’€, λ°”κΉ₯μͺ½ for loopμ—μ„œ iλ₯Ό 0λΆ€ν„° n-2κΉŒμ§€ μ¦κ°€μ‹œν‚΅λ‹ˆλ‹€.
  2. ν˜„μž¬ 인덱슀 iλΆ€ν„° λκΉŒμ§€μ˜ κ°’ 쀑 κ°€μž₯ μž‘μ€ 값을 μ°Ύμ•„ i번째 μœ„μΉ˜μ— λ†“μŠ΅λ‹ˆλ‹€.
  3. 이 과정을 n-1번 λ°˜λ³΅ν•˜λ©΄ λͺ¨λ“  값이 μ •λ ¬λ˜μ–΄ λ‚˜μ—΄λ©λ‹ˆλ‹€.
λ°˜μ‘ν˜•