[Algorithm log] SelectionSort

selectionSort는 말 그대로 선택해서 정렬한다.

작은 것을 찾아서 앞으로 보낸다. 이것이 전부다.

---

이 걸 또 정렬될 때까지 계속하는 거다.

---

새로운 배열을 만들어 가장 작은 값을 하나씩 넣어서 줄 수 도 있겠고, 원본 배열을 변경해서 하는 방법이 있을 수도 있겠다.

나는 원본 배열을 변경하는 방식으로 진행을 하려 한다.

역시 이번에도 반복문을 어떻게 구성해야 할지가 제일 중요하다.

일단 전체 요소만큼 에 사이클이 나올 것이고, 한 사이클마다 최솟값을 찾아야 한다. 또한 한 사이클을 돌게 되면 맨 앞은 제일 작은 수가 된다.

code

function selectionSort(array){
  for(let i=0; i<array.length-1; i++){ // 전체 사이클
    let minIdx = i;
    let temp;
    for(let j=i; j<array.length; j++){ // 한 사이클 
      // 한 사이클 내부에서 최소값의 인덱스를 찾는다.
      if(array[j] < array[minIdx]){
        minIdx = j;
      }
    }
    // 한 사이클이 끝나면 minIdx에는 최소값을 가지는 인덱스가 있다. 
    // 이 것을 가지고 앞에 값이랑 바꿔주면 된다.
    temp = array[minIdx];
    array[minIdx] = array[i];
    array[i] = temp;
  }
  return array;
}

이번에도 두 번째 for문이 중요하다. bubbleSort와는 달리 selectionSort는 앞쪽 요소가 채워지기 때문에 초기값이 하나씩 늘어난다.

bubbleSort와 비교해서 본다면 좋을 것 같다.