선택 정렬(Selection Sort)

선택 정렬(Selection Sort)의 특징

• 선택 정렬은 배열을 순회하면서 각 단계에서 배열의 나머지 부분 중에서 최소값을 찾아 최소값을 해당 단계의 시작점에 위치한 요소와 교환한다. 이 과정을 반복하여 정렬한다.
• 제자리 정렬(In-place sorting): 선택 정렬은 추가적인 배열을 필요로 하지 않으며, 배열 내에서 요소들의 위치를 교환하여 정렬한다.
• 불안정 정렬(Unstable sort): 선택 정렬은 동일한 값을 가진 요소의 상대적 순서가 정렬 과정에서 바뀔 수 있다. 동일한 원소가 초기 배열에서 가진 순서를 보존하지 않는다.
  • 예를 들어, [4, 6, 3, 4, 2, 8] 배열에 중복된 값이 있을 때, 정렬 과정에서 이 두 4 중 어느 하나가 다른 위치로 이동할 때, 그들 사이의 원래 순서가 바뀔 수 있다. 즉, 처음 배열에서 앞에 있던 4가 정렬 후에는 뒤에 있던 4 뒤로 이동할 수 있어, 두 4의 상대적인 순서가 뒤바뀌게된다.

selection-sort Animation 참고
sorting 참고

예를 들어, 아래와 같은 배열이 있다.
작은 수부터 큰 수로 나열한다고 했을 때,

첫 번째 순회

배열 전체 [4, 6, 3, 2, 8]에서 최소값 2를 찾아 첫번째 위치의 4와 교환한다.
2와 첫 번째 위치의 4를 교환합니다.
결과: [2, 6, 3, 4, 8]

두 번째 순회

남은 배열 [6, 3, 4, 8]에서 최소값 3을 찾아 현재 순회의 시작 위치인 6을 교환한다.
결과: [2, 3, 6, 4, 8]

세 번째 순회

남은 배열 [6, 4, 8]에서 최소값 4를 찾아 현재 순회의 시작 위치인 6을 교환한다.
4와 현재 순회의 시작 위치인 6을 교환합니다.
결과: [2, 3, 4, 6, 8]

네 번째 순회

남은 배열 [6, 8]에서 6이 이미 최소값이므로 교환 없이 유지한다.
결과: [2, 3, 4, 6, 8]

Big-O

• 시간 복잡도: O(n²) (best case : O(n²) (이미 정렬이 되어 있는 경우))
  • Best: O(n²)
  • Averrage: O(n²)
  • Worst: O(n²)
• 공간 복잡도: O(1)

장점

• 제자리 정렬(In-place sorting): 추가적인 메모리를 사용하지 않고, 주어진 공간만 이용해서 정렬한다.(공간 복잡도: O(1)) 메모리 공간을 절약할 수 있다.
• 선택 정렬은 교환 횟수가 비교적 적어, 데이터 이동이 비용이 많이 드는 상황에서 유리할 수 있다.

단점

• 데이터 양이 많아질수록 성능이 좋지 않다. 대용량 데이터를 처리할 때는 부적합하다.
• 불안정 정렬: 동일한 값을 가진 요소의 상대적 순서가 정렬 과정에서 바뀔 수 있다.
• 최선, 평균, 최악의 경우 모두 O(n²) 시간 복잡도를 가진다.

Javascript Algorithm

아래 소스는 선택 정렬을 알고리즘 구현한 소스이다.

function selectionSort(arr) {
    for(let i = 0; i < arr.length; i++) {
        let index = i;
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[index]) {
                index = [j]
            }
        }
        let temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
    return arr;
}

selectionSort([1, 5, 3, 2, 6]);