선택 정렬

📌 선택 정렬 (Selection sort)

맨 앞의 값과 뒤의 값들을 비교해 더 작은 값이 나오면 위치를 바꾼다.

• 시간 복잡도 : O(n^2)
  버블 정렬과 삽입 정렬에 비해 시간 복잡도가 좋지 않은 편이다.

선택 정렬 과정 애니메이션으로 보기
https://visualgo.net/en/sorting?slide=4-1

방법

1. 최솟값을 저장할 변수 만들기
   처음에는 최솟값을 배열의 첫 번째 요소로 세팅
2. 다음 항목들과 비교하여 최솟값 갱신 하기
   다음 항목이 더 작으면 다음 항목을 최솟값으로 갱신
   배열을 한 바퀴 돌며 더 작은 값을 새로 찾으면 갱신해줌
3. 처음 시작한 값이 최솟값이 아니라면 두 값의 위치를 바꿈
   최솟값이면 위치 바꾸지 않고 진행
4. 이미 정렬한 항목의 다음 항목부터 다시 시작하여 새로운 최솟값을 찾음.

예제

주어진 배열 오름차순 정렬하기

// LEGACY VERSION (non ES2015 syntax)
function sselectionSort(arr){
    for(var i = 0; i < arr.length; i++){
        var lowest = i; // 최솟값 위치
        for(var j = i+1; j < arr.length; j++){
            if(arr[j] < arr[lowest]){
                lowest = j; // 최솟값 위치 갱신
            }
        }
        // i가 이미 최솟값이면 swap 하지 않게 조건 추가
        if(i !== lowest){
            //SWAP!
            var temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

swap 과정을 ES2015 문법으로 작성한 코드

// ES2015 VERSION
function selectionSort(arr) {
  const swap = (arr, idx1, idx2) =>
    ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);

  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j;
      }
    }
    if (i !== lowest) swap(arr, i, lowest);
  }

  return arr;
}

selectionSort([0,2,34,22,10,19,17]);