선택 정렬 (Selection sort)

 

 

 

 

선택 정렬

선택 정렬은 데이터의 순서에 따라 위치는 이미 정해져 있고, 그 위치에 들어갈 원소를 선택하는 알고리즘입니다.

 

https://visualgo.net/en/sorting

 

선택 정렬의 진행 과정은 다음과 같습니다.

 

1. 먼저, 데이터들 중에 최소값을 찾습니다.
2. 찾은 최소값을 맨 앞에 위치한 데이터와 교화합니다.
3. 정렬된 맨 앞의 값을 제외하고 위와 같은 방식으로 데이터의 위치를 교환합니다.

선택 정렬은 버블 정렬과 반대로 회전마다 맨 앞의 데이터를 제외합니다. 선택 정렬은 n번의 회전 마다 n번째 데이터의 위치가 정해집니다.

 

시간 복잡도

선택 정렬은 버블 정렬과 마찬가지로 $O(n^2)$ 입니다. 한 번의 회전에 데이터 하나를 제외하기 때문에, 데이터가 n개 일 때, n-1 번의 순회가 필요합니다. 이를 수식으로 나타내면 아래와 같습니다. 

$$ (n-1) + (n-2) + ... + 2 + 1 = {n(n-1)} / {2} $$

 

 

 

자바스크립트 코드

function selectionSort(arr) {
  let minIndex;
  let swap;
  for(let i = 0; i < arr.length; i++){
     minIndex = i;
     for(let j = i + 1; j < arr.length; j++){
       if(arr[minIndex] > arr[j]){
         minIndex = j;
       }
     }
     swap = arr[minIndex];
     arr[minIndex] = arr[i];
     arr[i] = swap;
  }
  return arr;
}

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

 

장점

• 알고리즘이 단순하여 구현하기 쉽다
• 버블 정렬과 마찬가지로 제자리 정렬이므로, 별도의 메모리 공간을 필요로 하지 않는다.

단점

• 시간 복잡도가  $O(n^2)$로 많은 시간이 걸리고 비효율 적이다.
• 수가 중복된 경우 위치가 바뀔 수 있는 불완전(Unstable) 정렬이다.

 

정리

선택 정렬은 버블 정렬과 유사한 부분이 많습니다. 그러나 선택 정렬은 맨 앞에서 부터 정렬된다는 특징이 있습니다. 그 외에 버블 정렬과 시간 복잡도나 제자리 정렬이라는 공통점을 가집니다. 앞서 버블 정렬을 읽고 오신다면, 선택 정렬도 금방 이해하실 것이라고 생각합니다! : >