본문 바로가기
cs

Selection Sort (선택 정렬)

알고리즘 복습하기 정렬편 1탄

약 1분
#Algorithm#Sort

알고리즘 포스팅 하며 복습하기 (정렬편) 📊

  1. Selection Sort (선택 정렬)
  2. Insertion Sort (삽입 정렬)
  3. Bubble Sort (버블 정렬)
  4. Quick Sort (퀵 정렬)
  5. Merge Sort (병합 정렬)
  6. Heap Sort (힙 정렬)

선택 정렬이란?

선택 정렬은 배열 중 가장 작은 값을 찾아 맨 앞에 있는 값과 교환하고, 그 다음 작은 값을 찾아 두 번째 위치의 값과 교환하는 방식으로 정렬하는 알고리즘입니다.

post image

코드

 
const array = [1, 4, 2, 3, 5];
 
const selectionSort = (arr) => {
  const length = arr.length;
 
  for (let i = 0; i < length - 1; i++) {
    // 가장 작은 수를 가진 인덱스 변수 시작은 0
    let currentMinIndex = i;
 
    // currentMinIndex 다음 인덱스부터 배열의 "끝까지" 탐색한다
    for (let j = i + 1; j < length; j++) {
      if (arr[j] < arr[currentMinIndex]) {
        currentMinIndex = j;
      }
    }
 
    // 가장 작은 수를 가진 인덱스가 처음 시작한 인덱스와 다르다면 교환
    if (currentMinIndex !== i) {
      [arr[i], arr[currentMinIndex]] = [arr[currentMinIndex], arr[i]];
    }
  }
 
  return arr;
};
 
console.log(selectionSort(array)); // [1, 2, 3, 4, 5]

시간 복잡도

  • 가장 작은 값을 찾아야 하기에 매 루프마다 배열의 끝까지 탐색해야 합니다.
  • 최악의 경우 배열의 끝까지 탐색해야 하기에 시간 복잡도는 **O(n^2)**입니다.
  • Big O 표기법은 최악의 경우를 기준으로 표기