선택 정렬 (Selection Sort)

선택 정렬 소개

선택 정렬은 정렬 알고리즘 중 하나로, 버블 정렬과 비슷하지만 큰 값을 배열 끝에 위치시키는 대신 작은 값을 한 번에 하나씩 위치에 배열하는 방식입니다.

 

선택 정렬 동작 방식

1. 첫 번째 요소를 가장 작은 값으로 저장합니다.
2. 이 요소를 배열의 다음 요소와 비교하여 더 작은 수를 찾을 때까지 계속합니다.
3. 더 작은 수를 찾으면, 그 작은 수를 새로운 "최소값"으로 지정하고 배열의 끝까지 계속합니다.
4. "최소값"이 처음 시작한 값(인덱스)이 아닌 경우, 두 값을 교환합니다.
5. 배열이 정렬될 때까지 다음 요소로 이 과정을 반복합니다.

 

선택 정렬 의사 코드

{for i from 0 to n-1:
    minIndex = i
    for j from i+1 to n:
        if array[j] < array[minIndex]:
            minIndex = j
    if minIndex != i:
        swap(array[i], array[minIndex])}

 

선택 정렬 구현

다음은 ES2015(JavaScript) 버전의 선택 정렬 구현 예제입니다.

function selectionSort(arr) {
  const swap = (arr, idx1, idx2) =>
    ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);

  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j;
      }
    }
    if (i !== lowest) {
      swap(arr, i, lowest);
    }
  }

  return arr;
}

선택 정렬 빅오 복잡도

선택 정렬의 시간 복잡도는 O(n^2)입니다. 이는 이중 for 루프를 사용하여 배열의 각 요소를 비교하기 때문입니다. 선택 정렬은 다음과 같은 점에서 버블 정렬보다 효율적입니다.

• 스왑 횟수: 선택 정렬은 각 반복이 끝날 때 한 번만 스왑을 수행합니다. 이는 불필요한 스왑을 줄여줍니다.
• 단순성: 구현이 간단하여 이해하기 쉽습니다.

 

공간 복잡도

선택 정렬은 추가적인 배열을 사용하지 않고 주어진 배열 내에서 정렬을 수행하기 때문에 공간 복잡도는 O(1)입니다.

 

선택 정렬의 장점과 단점

장점

• 구현이 간단하고 이해하기 쉽습니다.
• 데이터의 양이 적을 때는 효율적입니다.
• 주어진 배열 내에서 정렬을 수행하기 때문에 추가 메모리가 필요하지 않습니다.

단점

• 시간 복잡도가 O(n^2)이기 때문에 대량의 데이터에 대해서는 비효율적입니다.
• 안정 정렬이 아닙니다. (같은 값의 요소들이 정렬 후에도 입력 순서가 유지되지 않을 수 있습니다.)

선택 정렬의 활용

선택 정렬은 데이터의 양이 적고, 간단한 정렬을 필요로 하는 경우에 유용합니다.

선택 정렬은 단순하지만, 알고리즘의 기본 개념을 이해하는 데 도움이 됩니다. 더 복잡한 알고리즘을 배우기 전에 선택 정렬을 이해하고 구현해 보는 것이 좋습니다.