선택 정렬(Selection Sort)

특징

• '가장 작은 것을 선택해서 가장 앞으로 이동시킨다'는 아이디어로 만들어진 알고리즘
• 데이터를 비교하며 가장 작은 것을 선택하고, 이를 가장 앞의 것과 교환(swap)해서 이동시킵니다. 그 다음 데이터부터 위 과정을 반복합니다.
• 교환(swap)하는 과정에서 임시 변수가 필요합니다.
• 교환하는 형태로 정렬이 진행되기 때문에 임시 변수를 제외하고는 추가적인 공간이 필요하지 않습니다.

효율

• 시간복잡도 - O(N²)
  • 비교 연산의 횟수: (N-1) + (N-2) + (N-3) + ... + 1 = N * (N - 1) / 2
  • 최선, 평균, 최악의 경우의 시간복잡도가 동일합니다.
• 공간복잡도 - O(N)

구현

function selectionSort(input) {
    for (let i = 0; i < input.length - 1; i++) {
        // i 번째 원소를 최소값으로 가정
        let minIndex = i;
        for (let j = i + 1; j < input.length; j++) {
            // 바로 다음 데이터부터 비교 시작
            if (input[minIndex] > input[j]) {
                // 최소값보다 해당 데이터가 작으면 인덱스를 변경
                minIndex = j;
            }
        }
        // 최소값이 변경됐다면, 가장 앞의 데이터와 교환(swap)
        if (i !== minIndex) {
            let temp = input[i];
            input[i] = input[minIndex];
            input[minIndex] = temp;
            console.log(...input);
        }
    }
}

let sample = [7, 3, 2, 8, 9, 4, 6, 1, 5];
selectionSort(sample);
/* 정렬 과정 출력
1 3 2 8 9 4 6 7 5
1 2 3 8 9 4 6 7 5
1 2 3 4 9 8 6 7 5
1 2 3 4 5 8 6 7 9
1 2 3 4 5 6 8 7 9
1 2 3 4 5 6 7 8 9
*/