[정렬] 선택정렬 + 최적화

선택정렬은 기초적인 정렬 알고리즘 중 하나로써

효율성이 좋다고 평가받지 못하는 알고리즘이지만,

그래도 기초가 가장 중요하다는 관점에서 꼭 배워야만 하는 알고리즘이라고 할 수 있다.

 

선택정렬은 버블정렬과 비슷하지만 뚜렷한 한가지 차이점이 있다.

• 버블정렬 : 최대값을 선택하여 연산하면서 계속 뒤로 빼나간다.
• 선택정렬 : 최소값을 제일 앞에 두는 방식으로 큰 값들을 뒤로 빼나간다.

 

최소값부터 앞에 쌓인다.

 

 

선택정렬 의사코드(Psuedocode)

• 배열의 첫번째 엘리먼트를 최소값 포인터로 일단 설정한다.
• 최소값 포인터를 다음 엘리먼트의 값과 비교를 하며, 현재 최소값 포인터보다 작은 값이 나올때까지 반복한다.
• 만약, 더 작은 값이 있을 경우, 최소값 포인터를 더 작은 값으로 재할당한다.
• 배열의 순회가 끝났다면, 가장 작은 값 엘리먼트와 배열에서 시작했던 지점의 엘리먼트를 교체해준다.
• 정렬이 될때까지 반복한다.

 

아래 코드를 보고 위의 의사코드를 보는 것이 나을 것 같다.

아래는 약간 naive한 풀이이다.

 

선택정렬(naive)

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let lowest = i                                 // (1)
        for (let j = i + 1; j < arr.length; j++) {     // (2)
        	if (arr[j] < arr[lowest]) lowest = j       // (3)
        }
        let temp = arr[i]
        arr[i] = arr[lowest]
        arr[lowest] = temp                             // (4)
    }
    return arr                                         // (5)
}

/*
(1) lowest를 외부 for문의 i값으로 설정한다. 
    선택정렬의 한 사이클이 완료되면 배열 맨 앞 엘리먼트는 최소값이 오기 때문에
    중복해서 연산할 필요가 없기 때문이다.
(2) j는 i + 1로 시작해서 i가 i를 연산하지 않게 한다.
(3) 만약 arr[j]가 최소값(arr[lowest])보다 작으면 lowest의 인덱스를 j로 바꿔준다.
(4) 내부 for문 순회가 끝났다면, 최소값의 위치를 앞쪽으로 빼준다.
(5) 최종적으로, 배열을 수정해서 리턴한다.
*/

• 외부 for문과 내부 for문의 연계를 중요시하게 보아야 한다.
• lowest의 초기값 설정에 관한 로직을 이해해야 한다.

 

위와 같은 풀이에서는 약간의 비효율성이 있고, 이를 해결해줄 수 있다.

예를들어 아래와 같은 비효율성이다.

 

N이 5만개라면 교체를 위해 5만개 x 3 정도의 연산이 들어가게 될 것이다.

 

 

배열을 순회했을 때, 0번 인덱스가 lowest라는 것을 알게 되었다면

굳이 교체를 해줘야할까?

그럴 필요는 없다.

따라서 간단한 조건문을 넣어 이러한 상황을 해결해볼 수 있다.

 

---

 

선택정렬 (약간의 최적화)

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
        }
        if (i !== lowest) { // 조건문만 하나 추가했다.
            let temp = arr[i]
            arr[i] = arr[lowest]
            arr[lowest] = temp
        }
    }
    return arr
}

 

i와 lowest의 값이 다를때만 엘리먼트를 교체해준다.( = lowest와 현재 인덱스가 같은 경우에는 교체하지 않는다. )

 

 

---

선택정렬의 효율성

 

선택정렬은 버블정렬만큼 효율적인 상황이 드물다.

하나씩 집어서 계속 정렬을 해야하는 알고리즘의 특성상 어떠한 최적화 방안을 마련하기가 어렵기 때문이다.

 

다만, 버블정렬의 경우 최대값을 계속 교체하면서 배열을 수정하는만큼 자잘한 연산이 많은 편인데

선택정렬의 경우 필요한 값만 골라서 마지막에 바꿔줌으로 아예 효율성이 없다고 할 수는 없다.