선택 정렬(Selection Sort)

Selection Sort는 Bubble Sort과 유사한 알고리즘으로, '해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘'이다.

Selection Sort와 Insertion Sort를 헷갈려하는 사람들이 종종 있는데, Selection Sort는 배열에서 '해당 자리를 선택하고 그 자리에 오는 값을 찾는 것'이라고 생각하면 편하다.

Process

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. (pass)
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

JavaScript Code

function selectionSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
  
  for (let i = 0; i < arr.length; i++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
   }
  
  if (arr[min] !== arr[i]) {
     swap(arr, i, min);
  }
  
  return arr;
}

• 첫번째 요소를 min이라는 변수에 저장합니다
• 반복문을 통해 min을 다음요소들과 비교하면서 가장 작은 값을 min에 할당합니다
• 만약 min이 최초에 저장한 값이 아니라면, 두 값을 swap 합니다
• arr의 모든 요소에 위 작업을 반복한 후 정렬된 배열을 리턴합니다

장점

• Bubble sort와 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

단점

• 시간복잡도가 O(n^2)으로, 비효율적이다.
• '불안정 정렬(Unstable Sort)' 이다.

 

* 틀린 부분이 있다면 말씀 부탁드립니다!