[JS 알고리즘] 선택 정렬(Selection sort)

선택 정렬의 작동원리

• 버블 정렬과 유사하지만, 큰 값이 아닌 작은 값부터 찾아서 정렬해나간다.
• 루프를 돌면서 가장 작은 값을 찾고, 찾게된 최소값을 해당 루프 시작점에 둔다.
• 시각화 사이트 참고 https://visualgo.net/en/sorting

선택 정렬 의사 코드

• 첫 번째 요소를 가장 작은 값으로 저장한다.
  - 더 작은 수를 찾을 때까지 이 가장 작은 값을 배열의 다음 항목과 비교한다.
  - 더 작은 숫자가 발견되면 더 작은 숫자를 새로운 "최소값"으로 지정하고 배열이 끝날 때까지 이 과정을 반복한다.
  - 배열의 끝까지 왔을 때, "최소값"이 처음에 시작한 값(인덱스)이 아니면 두 값을 바꾼다.
• 배열이 모두 정렬될 때까지 다음 요소에 대해 상기 모든 작업을 반복한다.

선택 정렬 코드

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

console.log(selectionSort([5, 3, 12, 4, 1]));
// [ 1, 3, 4, 5, 12 ]

선택 정렬의 성능

• Best Case : $O(n^2)$
  • 선택 정렬은 효율이 낮다.
  • 선택 정렬은 최소값을 찾기 위해 정렬되어 있는 정도와 상관없이 모든 요소를 다 확인해야만 한다. 따라서 거의 정렬되어 있는 배열을 정렬하는 경우, 선택 정렬이 제일 느리다.
• Worst Case: $O(n^2)$
• Average Case: $O(n^2)$