[TIL] 2024/04/11

💜 Key Point

병합 정렬, 삽입 정렬

💜 Today I Learned

[기술면접]

• 병합 정렬
  주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합친다.
  다른 정렬 알고리즘과 달리 인접한 값들 간에 상호 자리 교대가 일어나지 않는다.
  • 시간복잡도
    O(NlogN) - 전반적인 반복의 수는 점점 절반으로 줄어들기 때문

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }
  const mid = Math.floor(array.length / 2);
  const left = array.slice(0, mid);
  const right = array.slice(mid);
  return merge(mergeSort(left), mergeSort(right));

  function merge(left, right) {
    const resultArray = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        resultArray.push(left[leftIndex]);
        leftIndex++;
      } else {
        rightIndex++;
      }
    }
    return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
  }
}

console.log(mergeSort([5, 4, 3, 2, 1]));

ㅤ

• 삽입 정렬
  자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입한다.
  이미 정렬되어 있는 경우나 자료의 수가 적은 정렬에 매우 효율적이다.
  바로 옆의 데이터와 비교하기 때문에 안정적인 정렬이다.

  • 시간복잡도
    1) Best Case(이미 정렬된 경우)
    O(n) - 이미 정렬되어 있으므로 이동은 없으며 1번의 비교만 이루어진다.
    2) Worst Case(배열이 역순으로 정렬된 경우)
    O(n²)
    3) Avg Case
    O(n²)

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

console.log(insertionSort([4, 3, 2, 1, 5, -5, 20, 17]));