알고리즘, Sort, Selection Sort

선택 정렬(Selection Sort)은 단순한 정렬 알고리즘 중 하나로, 리스트에서 가장 작은 요소를 찾아 맨 앞의 요소와 교환하는 과정을 반복하여 정렬하는 방식입니다. 선택 정렬은 이해하기 쉽고 구현이 간단하지만, 시간 복잡도가 O(n^2)으로 비효율적입니다.

기본 개념

선택 정렬의 기본 개념은 다음과 같습니다:

1. 최소값 찾기: 리스트에서 현재 위치부터 끝까지 탐색하여 가장 작은 요소를 찾습니다.
2. 교환: 가장 작은 요소를 현재 위치의 요소와 교환합니다.
3. 반복: 리스트의 모든 위치에 대해 이 과정을 반복합니다.

예제

다음은 자바스크립트로 구현한 선택 정렬의 예제입니다.

function swap(arr, idx1, idx2) {
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let tempIdx = i;

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

    if (i !== tempIdx) swap(arr, i, tempIdx);
  }
  return arr;
}

console.log(selectionSort([0, 2, 34, 22, 10, 19, 17]));

// [ 0, 2, 10, 22, 34, 19, 17 ]
// [ 0, 2, 10, 17, 34, 19, 22 ]
// [ 0, 2, 10, 17, 19, 34, 22 ]
// [ 0, 2, 10, 17, 19, 22, 34 ]
// [ 0, 2, 10, 17, 19, 22, 34 ]

 

시간 복잡도

선택 정렬의 시간 복잡도는 다음과 같습니다:

• 최악의 경우 시간 복잡도: O(n^2)
  • 모든 요소를 비교해야 하므로 반복문이 중첩되어 시간 복잡도가 O(n^2)입니다.
• 평균 시간 복잡도: O(n^2)
• 최선의 경우 시간 복잡도: O(n^2)
  • 이미 정렬된 리스트에서도 모든 요소를 비교하므로 시간 복잡도는 여전히 O(n^2)입니다.

특징

1. 단순함: 선택 정렬은 이해하고 구현하기 매우 쉽습니다.
2. 제자리 정렬(In-place Sort): 별도의 추가 메모리를 거의 사용하지 않으며, 주어진 배열 내에서 정렬이 이루어집니다.
3. 안정성: 선택 정렬은 안정적이지 않습니다. 동일한 값의 요소들이 입력 순서를 유지하지 않을 수 있습니다.
4. 비효율성: 시간 복잡도가 O(n^2)으로, 큰 리스트에 대해서는 비효율적입니다. 따라서 실제로 사용되는 경우가 드뭅니다.

결론

선택 정렬은 교육 목적으로 많이 사용되는 단순한 정렬 알고리즘입니다. 이해하기 쉽고 구현이 간단하지만, 시간 복잡도 측면에서 비효율적이므로 실제로는 크기가 작은 배열을 제외하고는 잘 사용되지 않습니다. 대부분의 경우, 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)과 같은 더 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.