선택 정렬 알고리즘 (Selection Sort Algorithm)

선택 정렬(Selection Sort)은 간단하면서도 직관적인 정렬 알고리즘입니다. 배열을 순회하면서 가장 작은 값을 찾아서 해당 위치로 이동시키는 과정을 반복하여 정렬을 수행합니다.

선택 정렬의 동작 방식은 다음과 같습니다:

1. 주어진 배열에서 가장 작은 값(또는 큰 값)을 찾습니다.
2. 그 값을 현재 위치와 교환합니다.
3. 다음 위치로 이동하여 위의 과정을 반복합니다.
4. 배열의 모든 요소가 정렬될 때까지 반복합니다.

선택 정렬은 내부 루프를 통해 현재 위치 이후의 모든 요소를 비교하여 가장 작은 값을 찾습니다. 그 후에 최솟값을 현재 위치와 교환하여 최솟값이 정렬된 위치로 이동합니다. 이러한 과정을 반복하면서 배열이 정렬됩니다.

선택 정렬의 장점은 구현이 간단하고 이해하기 쉽다는 점입니다. 또한, 정렬 중간 단계에서 배열이 어떻게 정렬되었는지 확인할 수 있습니다. 하지만 선택 정렬의 단점은 시간 복잡도가 항상 O(n^2)으로, 배열의 크기가 커질수록 비효율적인 알고리즘이라는 점입니다.

따라서 선택 정렬은 작은 규모의 배열이나 정렬이 거의 완료된 상태에서 사용될 때 효과적일 수 있습니다. 그러나 대부분의 경우에는 다른 효율적인 정렬 알고리즘인 퀵 정렬, 병합 정렬, 힙 정렬 등을 고려하는 것이 좋습니다.

예시 1)

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;
}

// 예시 사용
const arr = [64, 25, 12, 22, 11];
const sortedArr = selectionSort(arr);
console.log(sortedArr);

위의 코드는 선택 정렬을 구현한 예시입니다. 선택 정렬은 입력된 배열을 반복하면서 현재 위치에서부터 나머지 요소들 중 가장 작은 값을 찾아서 현재 위치와 교환하는 과정을 반복하여 정렬을 수행합니다.

선택 정렬 알고리즘의 동작 방식은 다음과 같습니다:

1. 주어진 배열의 길이를 저장합니다.
2. 배열의 첫 번째 요소부터 마지막에서 두 번째 요소까지 반복합니다. (i = 0부터 n - 2까지)
3. 현재 위치 i를 최솟값으로 설정합니다. (minIndex = i)
4. 현재 위치 i 다음부터 마지막 요소까지 반복하면서 최솟값을 찾습니다. (j = i + 1부터 n - 1까지)
   • 현재 요소 arr[j]가 최솟값보다 작다면, 최솟값 위치를 갱신합니다. (minIndex = j)
5. 현재 위치 i와 최솟값 위치 minIndex가 다르다면, 두 요소의 위치를 교환합니다.
6. 반복이 끝나면 정렬된 배열을 반환합니다.

위의 코드를 사용하여 예시로 주어진 배열 [64, 25, 12, 22, 11]을 선택 정렬하여 오름차순으로 정렬한 결과 [11, 12, 22, 25, 64]를 출력합니다.