[알고리즘 | JS] sorting algorithm(정렬 알고리즘)2 - selection sort

Selection Sort (선택정렬)

-버블 정렬과 비슷하지만, 큰 값을 배열 끝에 위치시키는 대신 작은 값을 한 번에 하나씩 위치에 배열한다. 

• 버블 정렬과 마찬가지로 처음부터 끝까지 움직이지만, 실제 정렬된 데이터는 처음부터 누적되고 있다. 
• 첫 요소와 모든 요소를 비교 후, 비교 대상 중 최솟값을 찾아 마지막 swap을 통해 첫 요소와 최소값인 요소의 자리를 바꾼다(만일 첫번째 요소가 비교를 전부 끝냈을 때 최솟값이라면 자리를 이동하지 않는다->  noSwap). 

버블 정렬 만들기 tip 

• 우선 최솟값을 담을 변수를 만들어준다. 최솟값의 초기값은 첫번째 요소의 값으로 설정할 수 있다. 
• 저장하려는 변수 값은 최소값이 담긴 요소의 인덱스이다.
• 모든 단일 항복들에 대해 반복할 필요는 없다.
• 실제로 해야할 것은 그 이후의 다음 항목부터 시작하여 새로운 최솟값을 찾는 일이다. 
• 루프에 다른 루프와 단일 조건을 더하고 끝에서 바꾼다(swap)

2. 버블 정렬 예시

selectionSort.js

// selction sort example
{
  function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
      let lowest = i;
      for (let j = i + 1; j < arr.length; j++) {
        //console.log(i, j);
        if (arr[j] < arr[lowest]) {
          lowest = j;
        }
      }
      if (i !== lowest) {
        console.log(i, lowest);
        /*2 4
        3 6
        4 5
        5 6
        */
        //SWAP function
        let temp = arr[i];
        arr[i] = arr[lowest];
        arr[lowest] = temp;
      }
    }
    return arr;
  }
  console.log(selectionSort([0, 2, 34, 22, 10, 18, 17]));
  /*   
   [0, 2, 10, 17, 18, 22, 34]
  */
}

//ES2015 ver
{
  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;
  }
}

3. 선택 정렬의 시간복잡도

• 선택 정렬을 엄청나게 효율적이지는 않다.  => O(n^2) 
• 선택 정렬이 잠재적으로 버블 정렬보다 나은 시나리오는 단 한가지이다. -> 바로 SWAP의 수를 최소화하는 경우이다. 
• 버블 정렬은 매 비교 순간에 swap을 하지만, 선택 정렬은 각 루프가 끝날 때 한 번만 swap하기 때문이다.