선택정렬

선택정렬이란 무엇일까요?
기본적으로는 버블정렬과 비슷합니다. 대신에 최솟값을 찾아서 맨 앞에 놓는 방식의 정렬 입니다.

1. index 0과 1을 비교합니다. 둘 중 작은 값 -> 최솟값
2. 최솟값과 index2와 비교합니다 -> 새로운 최솟값 (index 0~2)
3. ... index(마지막)과 최솟값을 비교합니다. -> 배열에서의 최솟값 확인
4. 해당 최솟값을 index 0으로 이동시켜줍니다.
5. index 1부터 다시 최솟값 찾기 start 반복

선택정렬 구현 및 빅오

의사코드

• 최솟값을 저장할 변수를 지정합시다.
• swap기능을 구협해줍니다.
  (index 두개를 비교해서 작은 값을 최솟값으로 지정해주는 기능)
• 배열 전체를 돌면서 최솟값을 찾아줄 수 있도록 반복문을 작성해줍니다.
• index 0이 최솟값이 아니면 최솟값과 index 0의 위치를 바꿔줍니다.
• 최솟값을 찾은 index는 그대로 두고 그 이후의 값에서 다시 최솟값을 찾아줍니다.

// 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;
            }
        }
        if(i !== lowest){
            //SWAP!
            var temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

// 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]);

선택 정렬의 빅오 복잡도는 O(n^2) 입니다.
시나리오에 따라 버블보다 좋을 수도 있습니다. 스왑 최소화가 필요할때
버블 정렬의 경우 여러번의 스왑이 필요합니다. 한번 배열을 훑어볼때 여러번의 스왑이 일어날수도 있죠. 하지만 선택정렬의 경우 1번의 배열 순환에 최대 1번의 스왑이 일어나는 것을 알 수있습니다.