[알고리즘] 선택 정렬

✅ 선택 정렬 (Selection Sort)

❕ 기본 개념 

- 수열 중에서 최솟값을 검색한 후 왼쪽 끝 숫자와 교체하는 작업을 반복하며 정렬

- 최솟값을 찾을 때는 선형 탐색을 사용

- 숫자 비교 횟수는 (n - 1) + (n - 2) + ... + 1 ≈ n² / 2, 숫자 교체는 각 라운드 당 최대 1회

- 따라서 선택 정렬 시간 복잡도는 O(n²)

 

 

❕ 작동 방식 

 

Average Case

 

Worst Case (Reverse List)

 

 

✔ 구현 방법 (JS) 

function selectionSort(inputArr) {
  let n = inputArr.length;
 
  for (let i = 0; i < n; i++) {
    // Finding the smallest number in the subarray
    let min = i;
    for (let j = i + 1; j < n; j++) {
      if (inputArr[j] < inputArr[min]) {
        min = j;
      }
    }
    if (min != i) {
      // Swapping the elements
      let tmp = inputArr[i];
      inputArr[i] = inputArr[min];
      inputArr[min] = tmp;
    }
  }
  return inputArr;
}

 

 

참고자료

「알고리즘 도감」 中 2-3 선택 정렬

https://codepumpkin.com/selection-sort-algorithms/

https://stackabuse.com/selection-sort-in-javascript/