Selection Sort(선택 정렬)

Selection Sort

선택 정렬은 매우 단순한 정렬 알고리즘으로 구현하기 매우 쉬운 알고리즘이다. 선택 정렬 알고리즘은 이렇게 진행된다.

 

1. 먼저 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교환한다.
3. 이제 맨 앞을 제외하고 다시 순회하며 최소값을 찾는다.
4. 그 값을 맨 앞 위치 바로 다음 위치와 교체한다. ... 반복

 

버블 정렬이 각 회전이 끝날 때마다 맨 마지막 데이터의 위치가 정해졌던 것과 반대로

선택 정렬은 n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해진다.

다음의 그림을 보면 이해가 쉽다.

 

 

장점

선택 정렬도 위의 두 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있으며 알고리즘이 직관적이므로 이해하기도 쉽고 구현하기도 쉽다.

 

 

단점

선택 정렬은 최선의 경우에도, 최악의 경우에도 O(n^2)의 시간이 걸리는 만큼 성능이 매우 떨어진다.

선택 정렬을 자바스크립트로 구현해보았다.

 

function selectionSort (array) {
    for (let i = 0; i < array.length; i++) {
    let minIndex = i;
        for (let j = i + 1; j < array.length; j++) {
            console.log(j);
            if (array[minIndex] > array[j]) {
              minIndex = j;
            }       
            console.log(array)

        }
        if (minIndex !== i) {
            console.log(array,"gg")
            let swap = array[minIndex];
            array[minIndex] = array[i];
            array[i] = swap;
        }
    console.log(`${i}회전: ${array}`);
    }
    return array;
}
    


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

- OUTPUT

0회전: 1,5,7,3,2,1
1회전: 1,1,7,3,2,5
2회전: 1,1,2,3,7,5
3회전: 1,1,2,3,7,5
4회전: 1,1,2,3,5,7
5회전: 1,1,2,3,5,7
[ 1, 1, 2, 3, 5, 7 ]

항상 첫번째 자리를 기준으로 정렬하므로 i는 0부터 시작하고

첫번째 자리를 가장 작은 값이라고 가정하므로 minIndex 변수에 i를 담아준다.

i + 1번째 자리부터 순회하며 array[i]보다 작은 값이 있는지 검사한다.

검사가 끝나고 minIndex값이 i와 같지 않다면 그 값과 i번째 값을 교환한다.

 

1회전만에 정렬이 되어도 선택 정렬은 데이터가 정렬된 상태에서도 계속해서 순회하며

최소값을 찾는 과정을 하기 때문에 매우 비효율적인 정렬인 것을 확인할 수 있다.

 

Big O

• Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우
• Best Case: O(n^2): 이미 정렬이 되어있는 경우

선택 정렬은 위의 두 정렬과는 다르게 정렬이 이미 되어있는 경우에도 O(n^2)의 시간 복잡도를 가진다.

그 이유는 매번 정해진 자리에 올 수 있는 최소값을 찾아야하기 때문이다. 그렇기 때문에 성능이 매우 떨어진다.