선택 정렬 & 삽입 정렬

Selection Sort

Similar to bubble sort, but instead of first placing large values into sorted positon, it places small values into sorted position

진행하면서 가장 작은 요소, 즉 최솟값을 선택하고 맨 앞으로 배치한다.

Code

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

Big-O

선택 정렬은 엄청나게 효율적이지는 않다. n제곱의 시간 복잡도에 대한 얘기다.

선택 정렬이 잠재적으로 버블 정렬보다 나은 시나리오는 단 하나이다. 어떤 이유나 상황으로 스왑 수를 최소화하는 경우이다.

• 버블 정렬 : 가장 큰 항목을 끝까지 가져갈 수 있도록 계속 바꾼다.
• 선택 정렬 : 반복하여 많이 비교하지만, 각 루프가 끝날 때 한번만 바꾼다.

---

Insertion Sort

Builds up the sort by gradually creating a larger left half which is always sorted

이 정렬은 배열의 과반을 점차적으로 만들어 정렬을 구축한다. 과반은 항상 정렬되어 있다. 각 요소를 취하여 정렬되어 있는 절반 속 해당되는 위치에 배치한다.

한 번에 하나의 항목을 올바른 위치에 삽입해서 배열의 정렬된 부분을 점진적으로 구축하는 것을 확인할 수 있다.

Code

처음부터 시작하는 것보다 배열의 끝이나 중간에서 진행하는게 더 쉬운 이유는 실제로 거꾸로 수행해야 할 작업이 없기 때문이다.

function insertionSort(arr){
	var currentVal;
    for(var i = 1; i < arr.length; i++){
        currentVal = arr[i];
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

insertionSort([2,1,9,76,4])

Big-O

삽입 정렬은 O(n)에 가까운 시간 복잡도를 보여준다. 이는 삽입 정렬이 이미 정렬된 데이터에 대해 매우 효율적으로 작동한다는 것을 의미한다. 따라서 거의 정렬된 데이터를 다룰 때는 삽입 정렬이 퀵 정렬이나 머지 정렬과 같은 다른 정렬 알고리즘보다 더 나은 선택이 될 수 있다.