[정렬 알고리즘]Selection Sort

지난 시간 Sorting Algorithms이 무엇인지 그 중에서도 Bubble Sort에 대해서 알아보았다. 

👉 Link - Sroting Algorithms + Bubble Sort

 

선택 정렬 알고리즘(Selection Sort Algorithm)

데이터 배열을 내림차순 혹은 오름차순으로 나열하는 과정에서 사용되는 정렬 알고리즘 중 하나로 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬이다.

정렬 과정을 보면 첫 시작 값에서 시작하여 모든 데이터를 최소값을 찾은 뒤 교환한다. 교환된 최소값은 정렬이 된 것이며 다음 값에서 시작하여 다시 최소값을 찾아서 교환하기를 반복한다. 간단한 원리이다. bubble 정렬과 마찬가지로 swap이 발생한다. 선택 정렬의 의사코드를 살펴보자.

 

의사코드

1. 최소 값을 저장할 변수를 만든다. 처음에는 첫 번째 항목과 같게 설정할 수 있다. (정렬의 첫 번째 값이 가장 작은 값)

2. 가장 찾은 수를 찾을 때까지 배열의 항목에서 다음 항목으로 비교해나간다.

3. 더 작은 숫자가 발견되면, 더 작은 숫자를 새로운 최소값으로 지정하고, 배열의 끝까지 계속한다.

(실제로 최소값 그 자체를 저장하는 것이 아닌, 위치 인덱스임. 위치 인덱스를 가지고 swap이 발생함.)

4. 최소값이 처음에 시작한 값(index)가 아닌 경우 두 값을 바꾼다.

5. 다음 항목부터 시작하여 배열이 정렬될 때까지 반복한다. 매번 전체 배열을 살펴본다면, 언제가 같은 최소값을 가지게 된다. 

 

선택 정렬 구현 과정

function selectionSrot(arr) {
    for (let i = 0; i < arr.length; i++) {
        let lowest = i;
    }
    return arr;
}

selectionSrot([34, 22, 10, 19, 17])

기본적으로 모든 항목을 반복하는 것으로 시작해보았다. 최솟값을 가지는 변수를 만들고, i와 같도록 설정하였다. 

제일 처음에는 34가 최솟 값으로 설정이 될 것이고 옆의 항목들과 비교해 나간다. 

function selectionSrot(arr) {
    for (let i = 0; i < arr.length; i++) {
        let lowest = i;
        for (let j = i+1; j < arr.length; j++) {
            console.log(i, j)
        }
    }
    return arr;
}

두번째 loop를 j로 설정한 이유는 i가 0 즉, 첫번째 값이 정렬이 끝나면 그 값은 비교할 필요가 없기에 비교 대상에서 제외시키기 위함이다. 

function selectionSort(arr) {
    for(let i =0; i< arr.length; i++) {
        let lowest = i;
        for(let j = i+1; j < arr.length; j++) {
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        console.log('*******');
        console.log(arr);
        console.log('SWAPPING TO: ');
        // swap
        [arr[i], arr[lowest]] = [arr[lowest], arr[i]]
        console.log(arr);
        console.log('*******');
    }
    return arr;
}

selectionSort([34,22,10,19,17])

실행 결과

코드가 정상 작동한다. 하지만 위 코드는 최적화되어 있지 않다. lowest와 i 값이 같을 지라도 swap을 여전히 발생된다. swap이 발생할 필요가 없을 경우 swap의 발생을 막아준다. 

if(i !== lowest) {
  // swap
  [arr[i], arr[lowest]] = [arr[lowest], arr[i]]
}

위 코드로 조건을 생성하여 swap이 필요할 때만 swap하게끔 하였다. 

 

선택 정렬의 Big O 복잡도

모든 요소를 배열 속 다른 요소 모두와 비교해야 한다. 그러니 배열 길이가 길어지면 비교 횟수도 n에 n을 곱한, n 제곱 비율로 늘어난다. 선택 정렬이 버블 정렬보다 나은 경우는 단 하나 스왑 수를 최소화하는 경우이다. 버블 정렬의 작동 원리를 생각해보면 가장 큰 항목을 맨 뒤로 가져갈 수 있도록 스왑이 계속 발생한다. 선택 정렬의 경우 반복하여 많이 비교하지만 각 루프가 종료될 때 한번만 바꾼다. 흔치 않은 경우지만 어떤 이유로 메모리 쓰는 것을 고려하거나, 실제 스왑을 수행하는 것을 신경쓰고 있다면 선택 정렬이 나을 수 있다.

 

결론을 얘기 하자면, 선택 정렬은 쉬우나 성능적으로 좋은 정렬 알고리즘은 아니다. 하지만 다른 알고리즘들을 이해하는데에 충분한 도움이 될 수 있다.