Selection Sort Explanation

Problem Summary

Implement selection sort to sort an array in ascending order.

Detailed Explanation

이 문제는 **선택 정렬(Selection Sort)** 알고리즘을 구현하는 방법을 학습합니다. ## 핵심 개념: 선택 정렬 매 반복에서 최소값을 찾아 맨 앞으로 이동시킵니다. ### 알고리즘 1. 배열에서 최소값을 찾습니다 2. 최소값을 현재 위치와 교환합니다 3. 다음 위치에서 반복합니다 ### 코드 분석 ```javascript for (let i = 0; i < result.length; i++) { let minIdx = i; for (let j = i + 1; j < result.length; j++) { if (result[j] < result[minIdx]) minIdx = j; } [result[i], result[minIdx]] = [result[minIdx], result[i]]; } ``` ### 시각화 ``` [64, 25, 12, 22, 11] [11, 25, 12, 22, 64] // 11 선택 [11, 12, 25, 22, 64] // 12 선택 [11, 12, 22, 25, 64] // 22 선택 [11, 12, 22, 25, 64] // 완료 ``` ### 특징 - 교환 횟수가 적음 (O(n)) - 불안정 정렬 (같은 값의 순서가 바뀔 수 있음) - 구현이 단순함

Solution Code

solution.js

function selectionSort(arr) {
  const result = [...arr];
  for (let i = 0; i < result.length; i++) {
    let minIdx = i;
    for (let j = i + 1; j < result.length; j++) {
      if (result[j] < result[minIdx]) minIdx = j;
    }
    [result[i], result[minIdx]] = [result[minIdx], result[i]];
  }
  return result;
}

Key Concepts from This Problem

1. 선택 정렬

2. 최소값 찾기

3. 배열 교환

4. 정렬 알고리즘

Common Mistakes

✗ 원본 배열을 변경하지 않으려면 복사본을 만들어야 합니다

✗ 구조 분해로 교환할 때 순서에 주의하세요

✗ 이미 정렬된 배열에서도 O(n^2) 시간이 걸립니다

Hints

Hint 1: 매 반복에서 최소값을 찾아 현재 위치와 교환하세요.

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#알고리즘 #정렬 #선택정렬