μ½λ© ν
μ€νΈ/μκ³ λ¦¬μ¦
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]
- λ°°μ΄μ κΈΈμ΄λ₯Ό λ³μ nμ μ μ₯ν λ€, λ°κΉ₯μͺ½ for loopμμ iλ₯Ό 0λΆν° n-2κΉμ§ μ¦κ°μν΅λλ€.
- νμ¬ μΈλ±μ€ iλΆν° λκΉμ§μ κ° μ€ κ°μ₯ μμ κ°μ μ°Ύμ iλ²μ§Έ μμΉμ λμ΅λλ€.
- μ΄ κ³Όμ μ n-1λ² λ°λ³΅νλ©΄ λͺ¨λ κ°μ΄ μ λ ¬λμ΄ λμ΄λ©λλ€.
λ°μν