선택 정렬 ( selection sort )

선택 정렬 ( selection sort )

선택 정렬이란?

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 일반적으로 사람이 어떤 것을 크기 순서대로 정렬할 때 사용하는 방법과 유사한 방법이다. 나열된 것 중에 가장 작은 또는 큰 것을 선택해 앞 또는 끝으로 보내는 작업을 반복하면 최종적으로 크기 순서대로 정렬이 되는 방식이다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n^2) 만큼의 시간이 걸린다.

선택 정렬은 다음과 같이 작동한다.

1. 주어진 리스트 중에 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

코드와 설명

const selectionSort = arr => {
    let minIndex, temp;
    for ( let i = 0; i < arr.length-1; i++ ) { // 처음부터 마지막 하나전까지를 도는 반복문
        minIndex = i // 정렬되지 않은 배열 중 최솟값의 인덱스를 minIndex에 담음
        for ( let j = i+1; j < arr.length; j++ ) { 
            if ( arr[j] < arr[minIndex] ) { // 현재의 최솟값보다 작은 값이 있다면 minIndex를 해당 인덱스로 변경
                minIndex = j
            }
        }
        temp = arr[i]; // 정렬되지 않은 배열중 최솟값과 가장 앞의 값의 위치를 바꿔줌.
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

console.log(selectionSort([3,4,1,2]));

선택 정렬과 비슷하게 코드도 짧고 엄청 쉽지만, 그만큼 성능이 안좋아 실제로는 거의 안쓴다고 보면 된다고 함.

직관적이지만 인풋이 크다면 정렬할 때 좋지 않은 방법이다.