알고리즘 - 선택 정렬(selection sort) / 선택 정렬 구현

선택 정렬?

---

선택 정렬은 반복적으로 남은 배열 안에서 가장 작은 항목을 선택하는 정렬 알고리즘이다.

 

📌 선택 정렬의 동작 순서

1. 배열 안에서 가장 작은 항목을 찾는다.
2. 그다음으로 가장 작은 항목을 찾아 두 번째 항목과 교환한다.
3. 모든 배열이 정렬될 때까지 1-2단계를 반복한다.

 

📌 선택 정렬의 효율성

선택 정렬은 비교와 교환, 두 가지 단계를 포함하고 있다.

1. 비교 : 각 패스스루 내에서 각 값을 현재까지 찾은 최솟값과 비교한다.
2. 교환 : 최솟값을 올바른 위치에 있는 수와 교환한다.

 

배열의 크기가 N일 때, (N+1) + (N-2) + (N+3) + ... + 1번의 비교 연산이 필요하다. 교환은 한 번의 패스당 최대 한 번이 일어난다. 등차수열의 합 공식에 의하면 N(N-1)/2 이므로 O(N^2)이 된다.

 

📌 선택 정렬의 특징

1. 실행 시간이 입력에 민감하다.
   • 배열을 순회하면서 가장 작은 항목을 찾을 때 그다음으로 작은 항목이 어디에 있는지 정보를 주지 않는다.
2. 데이터의 이동을 최소화한다.
   • 교환 횟수가 배열의 크기에 선형으로 비례한다.

 

선택 정렬은 정렬이 되어있던 되어있지 않던 항상 일정한 속도를 가지게 된다. 그래서 최선의 경우, 평균의 경우, 최악의 겨우 모두 O(N^2)이다.

	최선의 경우	평균의 경우	최악의경우
선택 정렬	O(N^2)	O(N^2)	O(N^2)

 

Ex.

// array = [4,2,1,5,3]
const exchange = (array, i, j) => {
  [array[i], array[j]] = [array[j], array[i]]; // 현재 배열의 요소와 가장 작은 배열의 요소 교환.
}

const findMinIndex = (array, startIndex) => {
  let minIndex = startIndex;

  for(let i = startIndex; i < array.length; i++){
    if(array[minIndex] > array[i]){
      minIndex = i;
    }
  }

  return minIndex;
}

const selectionSort = (array) => {
  for(let i = 0; i <= array.length; i++){
    const minIndex = findMinIndex(array, i); // 가장 작은 값의 배열의 요소 찾음.

    if(minIndex === i ){ // 위치한 값이 이미 부분 배열에서 가장 작은 값일 때.
      continue;
    }

    exchange(array, i , minIndex); // [1,2,3,4,5]
  }
}