Selection Sort

선택 정렬

배열을 정렬하는 간단하면서 기본적인 비교 정렬 알고리즘입니다.

• 선택 정렬은 주어진 배열에서 가장 작은 값을 찾아서 맨 앞으로 이동시키는 과정을 반복하여 배열을 정렬합니다.
• 배열을 왼쪽과 오른쪽으로 두 부분으로 나누며, 왼쪽 부분은 정렬된 상태로 시작합니다.
• 오른쪽 부분에서 최솟값을 찾아 왼쪽 부분의 마지막 요소와 교환하고, 왼쪽 부분을 한 칸씩 확장하여 정렬합니다.
• 이 과정을 반복하여 배열이 정렬될 때까지 진행합니다.

주요 용도

• 선택 정렬은 구현이 간단하고 이해하기 쉬워 초기 학습자에게 적합합니다.
• 작은 규모의 배열을 정렬하는 데에는 효율적일 수 있습니다.

장점

• 구현이 간단하고 이해하기 쉽습니다.
• 추가 메모리 공간이 거의 필요하지 않습니다.

단점

• 성능이 좋지 않습니다. 배열의 크기에 따라 시간 복잡도가 크게 증가합니다.
• 불안정 정렬(Stable Sort)이기 때문에 동일한 값의 순서가 보장되지 않을 수 있습니다.

시간 복잡도

• 선택 정렬의 평균 및 최악의 시간 복잡도는 O(n^2)입니다.
• 최선의 경우에도 비교 연산과 교환 연산이 모두 발생하므로 성능이 좋지 않습니다.

사용에 적합한 상황

• 작은 크기의 배열을 정렬하는 경우에 적합합니다.
• 배열의 정렬 상태와 관계없이 항상 동일한 시간 복잡도를 가지기 때문에 입력 배열의 특성을 고려하지 않아도 됩니다.

사용에 부적합한 상황

• 큰 크기의 배열이나 정렬 속도가 중요한 경우에는 다른 정렬 알고리즘을 고려하는 것이 좋습니다.

주의사항:

• 선택 정렬은 불필요한 교환 연산을 수행할 수 있으므로 비효율적일 수 있습니다.

구현

JS

function selectionSort(data) {
  const length = data.length;

  for (let i = 0; i < length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < length; j++) {
      if (data[j] < data[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      [data[i], data[minIndex]] = [data[minIndex], data[i]];
    }
  }

  return data;
}

const result = selectionSort([10, 5, 8, 2, 1, 6]);
console.log(result); // [1, 2, 5, 6, 8, 10]

Python

import random

data = random.sample(range(100), 10)
print(data)

for i in range(len(data)-1):
    lowest = i
    for j in range(i+1, len(data)):
        print(i, j, '|', data[lowest], data[j])
        if  data[lowest] > data[j]:
            lowest = j
    print('Lowest:', data[lowest])
    data[i], data[lowest] = data[lowest], data[i]

    
print(data)