선택 정렬(Selection Sort)의 특징

• 매 루프마다 최소값 또는 최대값을 선택해서 정렬하는 알고리즘
• 비교 기반 정렬 알고리즘
• 안정적이지 않은 정렬(동일한 키 값이 있을 경우 순서가 바뀔 수 있음)
• 최악, 최적, 평균 모두 O(n^2)의 수행시간을 보임
• 제자리 정렬

알고리즘

1. 리스트를 순차적으로 탐색하면서 최대값/최솟값을 찾아낸다.
2. 찾아낸 최대값/최솟값을 리스트의 맨 앞, 또는 맨 뒤 인덱스와 교환한다.
3. 두번째에도 마찬가지로 순차적으로 탐색하여 찾아낸 최대값/최솟값을 리스트의 맨 앞, 또는 맨 뒤에서 두번째 인덱스와 교환한다.
4. 위의 과정을 반복한다.

구현

class SelectionSort {
    constructor(_list) {
        const list = _list;

        const swap = (list, a, b) => {
            const temp = list[a];
            list[a] = list[b];
            list[b] = temp;
        };

        const selectionSort = list => {
            if (Array.isArray(list)) {
                if (list.length === 0) {
                    return [];
                }

                for (let i = 0; i < list.length; i++) {
                    let minIndex;
                    for (let j = i; j < list.length; j++) {
                        if (!minIndex || list[minIndex] > list[j]) {
                            minIndex = j;
                        }
                        console.log(j)
                    }
                    swap(list, i, minIndex);
                }

                return list;
            }
        };
        return selectionSort(list);
    }
}

//------------------------------------

const data = [18, 15, 23, 28, 52, 59, 13];

const sortedData = new SelectionSort(data);

console.log(sortedData); // [13, 15, 18, 23, 28, 52, 59]