Selection Sort (with JavaScript)

# Selection Sort

Selection sort를 위키피디아에 검색해보면 다음과 같이 정의하고 있다.

"selection sort is an in-place comparison sorting algorithm"

하나씩 그 의미를 따져보면,

• In-place algorithm: an algorithm that operates directly on the input data structure without requiring extra space proportional to the input size. 즉, sorting 시 추가 메모리를 필요로 하지 않는다.
• comparison sort: 비교 연산자를 통한 정렬을 수행한다. 이러한 종류의 정렬은 최소 O(nlogn)의 시간 복잡도를 가진다.

Selection sort는 O(n²)의 시간 복잡도를 가지는 느린 정렬 방법이지만 보조 메모리가 제한적인 상황에서 유용하다고 한다.

 

# Process

• input list는 왼쪽의 sorted sublist와 오른쪽의 unsorted sublist로 나누어진다.
• 정렬 시작 시 sorted sublist는 비어있으며, unsorted sublist의 크기는 input list 전체이다.
• unsorted sublist의 최솟값을 갖는 item을 sublist의 가장 왼쪽의 item과 바꾼 후 sorted sublist로 간주한다.
• 해당 작업을 unsorted sublist가 비게 될 때까지 반복한다.

위 이미지에서 노란색이 sorted list, 흰 색이 unsorted list이다.

 

# JavaScript로 구현

function swap(array, leftIndex, rightIndex) {
  let temp = array[leftIndex];
  array[leftIndex] = array[rightIndex];
  array[rightIndex] = temp;
}

function selectionSort(array) {
  let min_index;
  for (let i = 0; i < array.length; i += 1) {
    min_index = i;
    for (let j = i + 1; j < array.length; j += 1) {
      if (array[j] < array[min_index]) {
        min_index = j;
      }
    }
    if (min_index !== i) {
      swap(array, i, min_index);
    }
  }
  return array;
}