선택 정렬 - 자리를 얻기 위한 경쟁

이번 포스팅 주제는 선택 정렬입니다.
선택정렬은 자료 구조 내의 한 위치를 두고 각 원소들이 순차적으로 경쟁을 하는 방식입니다.
이 문장만으로 어느정도 감이 오시지 않나요?
그러면 지금부터 선택정렬이 어떠한 방식으로 진행되는지 더 자세히 알아보겠습니다.

---

1. 선택 정렬 ( Selection Sort ) 이란?

 선택 정렬의 이름은 어떻게 지어지게 되었을까요?

 "선택 정렬"은 각 패스스루마다 원소를 넣을 위치는 하나로 고정 되어있고, 자료 구조를 순차적으로 탐색하면서 해당 위치에 어떠한 원소를 넣을지 "선택" 하는 알고리즘 이라는데서 이름이 유래되었습니다. 

 

---

 

2. 선택 정렬의 진행

  크기가 N인 배열을 오름차순으로 선택 정렬해 보겠습니다.
첫 패스스루에서는 배열의 첫 번째 ( 인덱스 : 0 )의 위치에 위치할 값 (배열 내 최솟값)을 찾는 것이 목표입니다.
오름차순이기에 배열을 탐색하면서 배열 내 최솟값을 찾습니다.
최소값을 확인한 후 해당 값을 선택하여 첫 번째 위치의 값과 교환해 줍니다.
다음 패스스루부터는 값이 확정된 첫 번째 원소를 제외 한 채로 앞에서 진행했던 단계를 반복합니다.
이렇게 패스스루를 반복해서 수행하게 되면 제외되는 데이터가 패스스루마다 하나씩 늘어나고 최종적으로는 배열이 오름차순으로 정렬된 채로 종료됩니다.

 

---

 

3. 선택 정렬의 코드 구현

function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
    	// 현재까지의 최소데이터의 위치 ( 초기 값은 현재 위치 )
        let minValueIndex = i;
        // 확정된 위치들을 제외한 범위 순회 시작
        for(let j = i + 1; j < arr.length; j++) {
        // 저장된 위치의 데이터보다 작은 데이터 발견 시 저장된 데이터의 위치 교체
            if(arr[minValueIndex] > arr[j]){
                minValueIndex = j;
            }
        }
        // 배열의 끝까지 탐색 후 저장 되어있는 데이터와 초기 위치의 데이터 교환
        if(i !== minValueIndex) {
            const tmp = arr[minValueIndex];
            arr[minValueIndex] = arr[i];
            arr[i] = tmp;
        }
    }
    return arr;
}

 

---

4. 선택 정렬의 효율성

• 시간 복잡도

1번째 패스스루에서  $N-1$ 단계
2번째 패스스루에서  $N-2$ 단계
....
마지막 패스스루에서 1단계로


(N−1)+(N−2)+...+1=$N(N-1)/2$
$O(N(N-1)/2)$ = $O(N^2)$ 가 나오게 됩니다.

• 공간 복잡도

주어진 공간 내에서 교환을 통해 정렬되므로 $O(N)$입니다.

 

---

 

4. 선택 정렬의 장단점

• 장점

* 구현이 단순하고 직관적
* 비슷한 거품 정렬 ( Bubble Sort )과 비교하였을 때 교환이 적어 상대적으로 빠름
* 자료 구조 내에서만 교환이 이루어져 별도 메모리 사용 없음 => 제자리 정렬

• 단점

* 시간복잡도가 $O(N^2)$로 비효율
* 중복된 값인 경우에는 입력 순서로 정렬 보장 하지 못함 => 불안정 정렬

---

마치며

이번 포스트에서는 선택 정렬에 대하여 알아보았습니다.
선택 정렬은 사람의 생각과 많이 닮아있습니다.
만일 알고리즘을 고민하지 않고 정렬 방법을 구현한다면 가장 많이 답으로 나올 정렬 방법이 아닌가 싶습니다.
때문에 쉽게 이해할 수 있는 알고리즘이었습니다.

 

출처

• https://gyoogle.dev/blog/algorithm/Selection%20Sort.html