[알고리즘] 선택 정렬 [Selection Sort]

[알고리즘] 선택 정렬 [Selection Sort]

선택 정렬은 간단하면서도 직관적인 정렬 알고리즘입니다.

이 알고리즘의 기본 아이디어는 배열을 순회하면서 가장 작은 (또는 가장 큰) 원소를 찾아 적절한 위치에 놓는 것입니다.

 

버블 정렬이 큰 값을 배열 끝에 위치시키는 것과 다르게

선택 정렬은 작은 값을 한 번에 하나씩 위치에 배열합니다.

선택 정렬이 잠재적으로 버블 정렬보다 나은 시나리오는 스왑 수를 최소화하는 경우입니다.

버블 정렬은 매번 스왑해서 순서를 바꾸지만 선택 정렬은 각 루프가 끝날 때 한번 바꿉니다.

메모리나 스왑수를 고려하는 경우라면 선택정렬이 좋을 수도 있습니다.

 

 

작동방식

1. 정렬되지 않은 배열에서 가장 작은 원소를 찾습니다.
2. 이 원소를 정렬되지 않은 부분의 첫 번째 원소와 교환합니다.
3. 정렬된 부분을 제외한 나머지 배열에 대해 이 과정을 반복합니다.

 

 

 

예시1

배열 [64, 25, 12, 22, 11]을 오름차순으로 정렬해봅시다.

1단계: 11이 가장 작으므로 64와 교환 [11, 25, 12, 22, 64]

2단계: 남은 원소 중 12가 가장 작으므로 25와 교환 [11, 12, 25, 22, 64]

3단계: 남은 원소 중 22가 가장 작으므로 25와 교환 [11, 12, 22, 25, 64]

4단계: 남은 원소 중 25가 가장 작음 (이미 올바른 위치에 있음) [11, 12, 22, 25, 64]

5단계: 마지막 원소는 자동으로 올바른 위치에 있게 됨 [11, 12, 22, 25, 64]

 

 

 

 

예시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;
      }
    }
    
    // 최소값과 i가 다를때만 순서 변환
    if (minIndex !== i) {
      // 원소 교환
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}

// 사용 예
const arr = [64, 25, 12, 22, 11];
console.log("정렬 전:", arr);
console.log("정렬 후:", selectionSort(arr));

 

 

 

 

선택 정렬의 특징

• 시간 복잡도: O(n^2) - 비효율적인 편입니다.
• 공간 복잡도: O(1) - 추가 메모리를 거의 사용하지 않습니다.
• 안정성: 불안정 정렬입니다. (동일한 값의 상대적 위치가 변경될 수 있음)
• 장점: 구현이 간단하고, 작은 리스트에 효과적일 수 있습니다.
• 단점: 큰 리스트에서는 비효율적입니다.

 

 

 

결론

선택 정렬은 이해하기 쉽고 구현하기 간단한 알고리즘이지만, 대규모 데이터에는 적합하지 않습니다.

그러나 알고리즘의 기본 개념을 이해하는 데 매우 유용하며, 작은 데이터셋이나 메모리 사용이 제한적인 환경에서는 여전히 유용할 수 있습니다.

 

 

 

 

참조!

https://www.udemy.com/course/best-javascript-data-structures/