본문 바로가기
JS sort_algolithm/UnStable Sort

Selection Sort(선택 정렬)

by Box 2021. 12. 9.
728x90

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)의 시간 복잡도를 가진다.

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

 





'JS sort_algolithm > UnStable Sort' 카테고리의 다른 글

Heap Sort ( 힙 정렬 )  (0) 2021.12.16
Quick Sort ( 퀵 정렬 )  (0) 2021.12.16