정렬 - 선택정렬

선택 정렬(Selection Sort)이란?

선택 정렬은 배열을 정렬하는 가장 기본적인 알고리즘 중 하나로, 다음과 같은 방식으로 동작합니다:

1. 배열에서 가장 작은 요소를 찾아 첫 번째 위치로 이동합니다.
2. 그다음, 두 번째 요소부터 남은 요소 중 가장 작은 값을 찾아 두 번째 위치로 이동합니다.
3. 이 과정을 반복하여 배열 전체를 정렬합니다.

🔹 시간 복잡도

• 최선, 평균, 최악의 경우 모두 O(n²)
• 이유: 각 요소를 확인하며 남은 요소에서 최솟값을 찾기 때문

 

 

 

const selectionSort = (arr) => {
  const len = arr.length;
  
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;

    // i 이후의 요소 중 최소값 찾기
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // 최소값이 현재 위치(i)와 다르면 교환
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
};

// 예제 실행
console.log(selectionSort([64, 25, 12, 22, 11])); 
// 출력: [11, 12, 22, 25, 64]

첫 번째 반복문 (i)

• 배열을 한 요소씩 순회하면서 정렬할 위치를 결정합니다.
• minIndex를 현재 i로 설정합니다. (즉, 현재 위치의 값이 최소값이라고 가정)

두 번째 반복문 (j)

• i+1부터 배열 끝까지 반복하면서 현재 최소값(minIndex)보다 작은 값이 있는지 확인합니다.
• 작은 값을 찾으면 minIndex를 해당 인덱스로 업데이트합니다.

값을 교환 (swap)

• minIndex가 i와 다르면(즉, 더 작은 값이 발견되었으면)
  **ES6 비구조화 할당(Destructuring Assignment)**을 사용하여 값을 교환합니다.
• [a, b] = [b, a]는 temp 변수를 사용하지 않고 값 교환을 간결하게 처리하는 방법입니다.

 

질문

[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; 
위 코드만 있어도 되는데 왜 분기 처리하는지?

// 최소값이 현재 위치(i)와 다르면 교환
if (minIndex !== i) {
  [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}


[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
이 줄은 항상 값 교환(Swap) 을 수행하는데,
만약 minIdx === i라면 자기 자신과 교환하는 불필요한 연산이 발생합니다

for (let i = 0; i < arr.length - 1; i++)  왜 arr.length - 1 까지 반복?

이유는 마지막 요소는 자동으로 정렬되기 때문입니다.

선택 정렬(Selection Sort) 의 동작 방식을 살펴보면,
각 반복(i)에서 가장 작은 값을 찾아 현재 위치(i)와 교환하는 방식입니다.

배열 크기가 n일 때,

첫 번째 루프(i=0)에서 최소값을 찾아 arr[0]과 교환
두 번째 루프(i=1)에서 최소값을 찾아 arr[1]과 교환
...
마지막(i=n-2) 루프에서 arr[n-2]을 정렬하면 자동으로 arr[n-1]도 정렬됨!
즉, i=n-1까지 갈 필요 없음.



const arr = [64, 25, 12, 22, 11];

for (let i = 0; i < arr.length - 1; i++) {  //  마지막 원소 전까지만 반복
    let minIdx = i;

    for (let j = i + 1; j < arr.length; j++) {
        if (arr[minIdx] > arr[j]) minIdx = j;
    }

    if (minIdx !== i) {
        [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
}

console.log(arr);  // [11, 12, 22, 25, 64]


i = 0 → [11, 25, 12, 22, 64]
i = 1 → [11, 12, 25, 22, 64]
i = 2 → [11, 12, 22, 25, 64]
i = 3 → [11, 12, 22, 25, 64] (이미 정렬 완료)
마지막 i=4일 때는 실행할 필요 없음! (자동 정렬됨)

만약 arr.length까지 하면?

마지막 반복(i = arr.length - 1)에서는 내부 루프(j = i + 1)가 실행되지 않음
불필요한 반복이 발생하여 성능 저하 가능