thisyujeong.dev

JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트

선택 정렬 (Selection Sort)

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

첫 번째 루프에서는 최솟값을 첫 번째 위치에 넣고, 두 번째 루프에서는 남은 값들 중 최솟값을 두 번째 위치, ...

정렬 과정

[19, 44, 38, 5, 47, 15] 배열을 오름차순으로 정렬해보자.

• 1회전: [19, 44, 38, 5, 47, 15]
  • 첫 번째 값(19)을 최솟값(5)을 탐색해 교환
  • 1회전 결과: [5, 44, 38, 19, 47, 15]
• 2회전: [5, 44, 38, 19, 47, 15]
  • 두 번째 값(44)을 최솟값(15)을 탐색해 교환
  • 2회전 결과: [5, 15, 38, 19, 47, 44]
• 3회전: [5, 15, 38, 19, 47, 44]
  • 세 번째 값(38) 보다 작은 최솟값이 없음으로 교환하지 않음
  • 3회전 결과: [5, 15, 19, 38, 47, 44]
• 4회전: [5, 15, 19, 38, 47, 44]
  • 네 번째 값(47)을 최솟값(44)을 탐색해 교환
  • 2회전 결과: [5, 15, 19, 38, 44, 47]

의사코드

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j;
      }
    }
    if (i !== lowest) {
      let temp = arr[i];
      arr[i] = arr[lowest];
      arr[lowest] = temp;
    }
  }
  return arr;
}
 
selectionSort([34, 22, 10, 19, 17]); // [10, 17, 19, 22, 34]

시간 복잡도

• Best: O(n²)
• Worst: O(n²)
• Average: O(n²)