선택정렬(Selection Sort) 이란

정렬?

정렬은 데이터를 특정 기준에 따라 순서대로 나열하는 방법이다.
문제 상황에 따라 적절한 정렬 알고리즘을 선정하여 사용해야 한다.

 

이번 포스팅에서는 정렬 중 알고리즘이 단순한 선택 정렬에 대해서 알아본다.

---

선택 정렬(Selection Sort)

정해진 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다.

 

처리되지 않은 데이터 중, 가장 작은 데이터를 선택해 앞의 데이터와 순서를 바꾼다고 이해할 수 있다.

 

선택 정렬의 과정은 다음과 같다.

 

1. 처리되지 않은 데이터 중 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 처음 위치를 뺀 나머지 배열을 같은 방식으로 교체한다.

 

gif를 통해 바로 이해해보자.

출처 : https://dev-lagom.tistory.com/37

 

알고리즘을 JS코드로 구현해봤다.

 

  const arr = [4, 6, 3, 2, 0, 1, 5];

  function selectionSort(arr){
      const len = arr.length;

      for (let cur = 0; cur < len; cur++){
          let idx = cur;
          for (let j = cur + 1; j < len; j++){
              if(arr[idx] > arr[j]){
                  idx = j;
              }
          }
          [arr[cur], arr[idx]] = [arr[idx], arr[cur]];
      }
      return arr;
  }

  console.log(selectionSort(arr)); // [0, 1, 2, 3, 4, 5, 6]

for문의 cur 변수는 '정해진 위치'를 의미하고,

idx 변수는 '가장 작은 값의 위치'를 담고 있다.

그래서 '정해진 위치'에 있는 값과 '가장 작은 값의 위치'에 있는 '가장 작은 값'을 스왑해줌으로서,  오름차순 정렬을 수행한다.

---

선택 정렬의 시간복잡도

선택 정렬은 매번 이중 반복문을 거치며 선형탐색을 수행한다.

원소의 개수인 N회 만큼 가장 작은 수를 찾아 맨 앞으로 보내야 한다.

 

첫 비교(=첫 회전)에서의 비교 횟수는 인덱스 1부터 N-1까지 총 N-1회이다.

두번째 비교는 인덱스 2부터 N-1까지 총 N-2회이다.

...

N-1번째 비교는 N-2 인덱스와 N-1 인덱스와 비교하면 되고

마지막 비교는 마지막 인덱스에 위치한 값은 최댓값이므로 수행할 필요가 없다.

 

그러므로, 전체 연산 횟수는 다음과 같다.

 

(N-1) + (N-1) + (N-2) + ... + 2 + 1
= (N * (N-1) / 2 ) = (N^2 - N) / 2

 

총 O(N^2)의 시간 복잡도로 표현된다.

---

선택 정렬의 공간복잡도

선택 정렬은 동일한 배열 내에서 수행한다.

• 주어진 배열 안에서 인덱스끼리 Swap을 통해 정렬이 수행된다.

그러므로 O(N) 만큼의 공간복잡도를 가진다.

---

장점

알고리즘이 단순하다.

인덱스마다 비교하는 횟수는 많지만, 교환 횟수는 1회밖에 되지 않는다.

• 그러므로, 인접 인덱스간 많은 교환이 일어나는 거품 정렬(Bubble Sort)에 비해 효율적이다.

주어진 배열 안에서 인덱스끼리 Swap을 통해 정렬이 수행되므로 공간 효율적이다. (= 제자리 정렬)

---

단점

시간복잡도가 O(N^2)이다.

불안정 정렬이다.(= 중복 값이 입력 순서와 동일하지 않게 정렬될 수 있는 알고리즘)

• 예를 들면, `5` 7 5 3 2를 선택정렬로 정렬하면, 2 3 5 `5` 7 의 순서로 정렬된다.