[Algorithm] 선택 정렬 (Selection Sort)

선택 정렬?

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

Sorting Algorithm Animations Sort Animation // Visualgo Sort Algorithm GIF

알고리즘 과정

• 주어진 배열에서 첫 번째 원소를 선택하고 첫 번째 원소와 비교하면서 최솟값을 찾는다.
• 최솟값을 첫 번째 원소와 swap한다.
• 정렬된 값은 제외하고 나머지 배열을 같은 방법으로 반복한다.

알고리즘 구현

function selection(arr) {
  for(let i = 0; i < arr.length; i++) {
    let min = i;
    for(let j = i+1; j < arr.length; j++) {
      if(arr[j] < arr[min]) min = j;
    }
    if( i !== min ) {
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }
  return arr;
}

시간복잡도와 공간복잡도

• 최선, 평균, 최악의 경우 시간복잡도 O(n^2)으로 동일하다.

• swap을 통해 정렬이 수행되므로 O(n)이다.