선택 정렬

선택 정렬에 대해 알아봅니다.

선택 정렬

 

선택 정렬

 

1. 선택 정렬이란 무엇이고, 어떻게 이뤄지는가?

2. 코드로 살펴보기

 

1. 선택 정렬이란 무엇이고, 어떻게 이뤄지는가?

 가장 큰 수, 혹은 가장 작은 수를 선택해서 정렬을 반복하는 과정이다. 이중 반복문을 사용하며, 각 회차마다 정렬이 되지 않은 모든 요소를 조회하여 가장 큰 수(가장 작은 수)를 찾아 제일 오른쪽(왼쪽)으로 위치를 변경한다.
 이중 반복문을 사용하므로 시간 복잡도는 항상 n^2으로, 배열의 길이가 늘어날수록 시간이 급격히 늘어난다.

2. 코드로 살펴보기

function selectionSort(arr) {
  const len = arr.length;

  for (let i = 0; i < len - 1; i++) {
  // 전체 요소를 조회하면서 가장 작은 수의 인덱스를 찾는다.
  // len - 2 인덱스까지 정렬을 하면, 마지막 인덱스인 len - 1도 자동 정렬이 되기 때문에
  // len - 1 인덱스 까지만 반복문을 실행한다.
  
    let minIndex = i;
    // 반복문을 시작하는 인덱스가 가장 작은 수의 인덱스라고 가정하고 시작한다.

    for (let j = i + 1; j < len; j++) {
    // i 다음 인덱스부터 시작해서 남은 모든 요소를 조회한다.
    
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
        // 만약 현재까지 찾은 가장 작은 수보다 더 작은 수가 나오면, 
        // 해당 수의 인덱스로 변경한다.
        
      }
    }

    if (i !== minIndex) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
      // 조회하면서 찾은 가장 작은 수의 위치를 가장 왼쪽으로 변경한다.
      
    }
  }

  return arr;
}