[JS] 선택정렬

1. 선택 정렬

 선택정렬은 정렬 알고리즘의 하나이다.

 

 동작 순서는 별거 없다. 이 한마디만 기억하면 된다.

 

최소 값을 맨 앞으로 보내라

 

2. 동작 순서

 

 이것이 무슨 말입니까...?

 

생각이 든다면, 간단한 예를 들어보도록 하겠다.

 

선택 정렬의 동작순서를 설명을 하기 위해 다음의 리스트 값으로 예를 들어보도록 하겠다.

 

[그림 1] 입력 값

 

우리는 선택정렬을 이용해서 이 리스트 값을 오름차순으로 정렬하려고 한다.

 

먼저, 첫 번째 요소 5에서부터 리스트 끝인 6까지 탐색해서 최솟값을 찾도록 한다. 최솟 값은 1이 나온다.

 

[그림 2] 최솟 값 1

찾은 최솟 값 1을 맨 앞 요소와 스와핑한다.

 

[그림 3] 최솟 값 1과 맨 앞 요소 5를 스와핑한다.

 

그리고 두 번째 요소 10에서부터 리스트 끝인 6까지 탐색해서 최솟 값을 찾도록 한다.

 

[그림 4] 최솟 값 2

최솟 값은 2가 나온다. 그 후 찾은 최솟 값을 10과 스와핑하여 맨 앞으로 보낸다.

 

 

[그림 5] 최솟 값 5

그리고나서 5부터 최솟값 탐색을 시작한다. 최솟값은 5자신이 되니까 그대로 나두면 된다.

 

뭐.. 이런 순서로 동작해서 오름차순으로 정렬된다고 생각하면 된다.

 

3. 시간 복잡도

 위의 예시로 선택정렬은 총 몇번의 탐색을 했는지 알 수 있다.

 

1. [5, 10, 1, 2, 6]
2. 1 [10, 5, 2, 6]
3. 1 2 [5, 10, 6]
4. 1 2 5 [10, 6]
5. 1 2 5 6 [10] 

  5 + 4 + 3 + 2 + 1의 탐색횟수는 총 15번이라는 것을 알 수 있다.

  

 이를 수학적으로 계산하면,

$$ \frac{5\times(5+1)}{2} $$

가 되고, 5를 n으로 둔다면,

$$ \frac{n\times(n+1)}{2}$$

가 된다.

 

따라서, 컴퓨터공학적으로 n을 매우 큰 수로 가정하기 때문에

 

2로 나누는 것은 사실상 나누나마나 수치가 비슷하다.

 

따라서, 선택정렬의 평균 복잡도를 빅오 표기법으로 나타내면

$$ O(n^2) $$

이며, 이 수치는 정렬에서는 가장 큰 시간복잡도를 나타내는 것이기 때문에

 

선택정렬은 비효율적인 정렬이라고 할 수 있다.

 

위키에 따르면

 

선택정렬은 메모리가 제한적인 경우에 사용하며, 이 경우에 성능 상의 이점을 볼 수 있다고 한다.

 

4. 프로그램 코드

선택 정렬을 코드로 작성하면 다음과 같다.

 

const selectSort = (arr) => {
  for(let i=0; i<arr.length; i++){
    let min = 999, idx=0, temp = 0;
    for(let j=i; j<arr.length; j++){
      if(min >= arr[j]){
        min = arr[j];
        idx = j;
      }
    }
    temp = arr[i];
    arr[i] = min;
    arr[idx] = temp;
  }
  return arr;
}

 

5. 참고자료

1.  동빈나 - 2강 정렬 알고리즘의 개요와 선택정렬(Selection Sort)[ 실전 알고리즘 강좌(Algorithm Programming Tutorial) ]

2. 선택 정렬 위키백과