Selection Sort

본 문서는 2021년 12월 28일 에 작성되었습니다.
본 코드는 2022년 3월 29일 에 작성되었습니다.

Selection Sort 는 정렬 알고리즘 중에 가장 작성하기 쉽습니다.
그러나 다음과 같은 단점이 있습니다.

1. 낮은 생산성
2. 충분하지 못한 안전성

Code

Test Selection Storage 를 이용 합니다.

pickIdx 에 배열 첫 공간값 0 을 넣고 loop 를 시작합니다.
loop 한 번 당 최소의 값의 Idx 를 Test Selection Storage 에 넣습니다.

약 loop * idx 번 반복하게 되며, 따라서 O(n^2) 입니다.

export function selectionSort([length, numbers]) {
    const nums = [...numbers];

    let pickIdx = 0;
    for (let loop = 0; loop < length-1; loop++) {
        
        pickIdx = loop;
        for (let idx = loop + 1; idx < length; idx++)
            if (nums[pickIdx] > nums[idx]) pickIdx = idx;

        [nums[pickIdx], nums[loop]] = [nums[loop], nums[pickIdx]];
    }

    return nums;
}

Selection Sort 란?

길이가 n 인 배열이 있을 때,
1번 째 요소를 기준으로 배열의 경계까지 조회하며 비교합니다.
결과적으로 가장 작은 값과 그 자리를 바꾸게 됩니다.

분석

0. 안정성 : 구현에 따라 다름
1. 최적 상황 : O(n^2)
2. 평균 상황 : O(n^2)
3. 최악 상황 : O(n^2)
4. 공간복잡도 : O(1) // 임시변수 정도의 공간만 할당됨

Ref

[알고리즘] 선택 정렬이란?
Selection Sort - The Sorting Algorithm Family Reunion